Java in place array

[Solved] 3 Examples to reverse an Array in Java — Example Tutorial

Hello guys, today we are going to see another common coding question from interviews — how do you reverse an array in Java? This is a popular array-based coding problem and often asked programmers during the first few rounds of interviews to check if they can code or not. Well, there are multiple ways to solve this problem and we will see three common ways to ever an array in Java. This method applies to all kinds of arrays like string array or integer array or even with arrays of objects because it’s not focused on data types. The first way to reverse an array is by reversing it in a brute force way, without using any additional data structure or library method.

Yes, you can reverse the array by writing your own function, which loops through the array and swaps elements until the array is sorted. That’s actually should be your first approach to coding interviews.

Later you can impress the interviewer with a couple of other tricks, which are specific to the Java development world. For example, you can reverse an array by converting an array to ArrayList and then use this code to reverse the ArrayList.

You can also use the Apache Commons ArrayUtils.reverse() method to reverse an array in Java. This method is overloaded to reverse byte , short , long , int , float , double, and String array. You can use any of the methods depending upon your array type.

By the way, if you are new to Java programming and not familiar with basic Java concepts like data types then I highly recommend you to join a comprehensive course to learn Java in a structured way. If you need a recommendation, I suggest checking out The Complete Java Masterclass course by Tim Buchalaka on Udemy. This 80-hour long course is the most comprehensive as well as up-to-date courses to learn Java online.

3 Ways to Reverse an Array in Java

Now that you have understood the problem, let’s see different ways to solve this problem in Java. You will learn how to reverse a given array without using any third-party library as well as how using a library can make your job much easier.

1. Reverse a given Array in Place

This is one of the simplest ways to reverse an array in Java. This algorithm iterate over an array and swap elements until you reach the midpoint. This is also known as reversing an array in place because no additional buffer is used.

for(int i=0; iarray.length/2; i++)< int temp = array[i]; array[i] = array[array.length -i -1]; array[array.length -i -1] = temp; >

The time complexity of this algorithm is O(n/2) which is O(N) because we are iterating over array till midpoint only. This should be your solution on interviews, the rest of the two methods are for practical use purposes.

Btw, if you are preparing for Java interviews and solving coding questions to gain confidence, then you should also check Data Structures and Algorithms: Deep Dive Using Java course on Udemy one of the best courses to learn Algorithms and Data Structure like an array and binary tree to do well on Java Interviews.

2. Reverse an Array using ArrayList in Java

This is another simple way to reverse an array in Java is by first converting the array to List and then using the Collections.reverse() method to reverse the ArrayList. This method takes a List and reverses the element in linear time.

You should use this approach if you need to reverse an array in your project. You can reverse int , String, or any type of array by using this method.

Let’s see an example of reversing a String array in Java:

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; /** * Simple Java Program to reverse an array * * @author Javin Paul */ public class ArrayReverse < public static void main(String args[]) < String[] typesOfInsurance = "Life Insurance", "Car Insurance", "Health Insurance">; System.out.println("array before reverse: " + Arrays.toString(typesOfInsurance) ); List listOfProducts = Arrays.asList(typesOfInsurance); Collections.reverse(listOfProducts); String[] reversed = listOfProducts.toArray(typesOfInsurance); System.out.println("array after reverse: " + Arrays.toString(reversed) ); > > Output array before reverse: [Life Insurance, Car Insurance, Health Insurance] array after reverse: [Health Insurance, Car Insurance, Life Insurance]

You can see the order of elements is reversed in the final array returned by the toArray() method of the List class.

Btw, if you are struggling with algorithms and data structure then please check the new Grokking Algorithm by Aditya Bhargava. One of the best algorithm books for beginners. He has done a great job of explaining various algorithms with real-world examples.

I know learning algorithms are not easy and the books we have like Introduction of Algorithms which is also not very easy for beginners, hence I am promoting this book to all beginner programmers. Good knowledge of data structure and algorithms goes a long way in your career and it doesn’t matter whether you do coding in Java or C++, these concepts remain the same.

The only drawback of this book is examples are given in Python, which is not really a drawback if you have a basic understanding of Python but I understand a Java book on the same line would have been much better.

I did learn a lot from that book because concepts are independent of programming language but if you still need Java examples, you can combine that book with a course like Data Structures for Coding Interviews in Java, an interactive course from Educative.

Solution 3 — By using ArrayUtils.reverse()

Apache Commons is an open-source library that provides several utility libraries that are essential for software development in Java. In fact, one should by default add this library into their Java projects to complement JDK. Apache commons-lang provides an ArrayUtils class that has overloaded reverse() methods to reverse int , float, or object arrays in Java. This method also reverses the given array in place i.e. it doesn’t return a new array.

import java.util.Arrays; import org.apache.commons.lang3.ArrayUtils; /** * Java Program to reverse an array using Apache Commons Lang ArrayUtils * class. * * @author Javin Paul */ public class Pattern < public static void main(String args[]) < String[] assetClasses = "bond", "equity", "gold", "real estate">; System.out.println("Array before reversing: " + Arrays.toString(assetClasses)); ArrayUtils.reverse(assetClasses); System.out.println("Array after reversing: " + Arrays.toString(assetClasses)); > > Output Array before reversing: [bond, equity, gold, real estate] Array after reversing: [real estate, gold, equity, bond]

You can see we have managed to reverse the array in just one line now. The ArrayUtils class is from Apache commons-lang and you need to add commons-lang3-3.4.jar into your application’s classpath. Alternatively, if you are using Maven then you can also add the following dependency in your pom.xml file.

 org.apache.commons commons-lang3 3.4 

That’s all about how to reverse an array in Java. You have learned three different ways to solve this problem, first, you can the in-place algorithm to reverse array if you were asked to solve this problem in interviews. Second, you can use the ArrayList class if you need to reverse the array in your project, and last, you can use the utility method ArrayUtils.reverse() from Apache commons-lang library if your project is already using it.

• How to implement a binary search in an array? (solution)
• Top 5 Courses to learn Data Structure and Algorithms (courses)
• How to reverse an array in place in Java? (solution)
• How to check if an array contains a particular value? (solution)
• How to find all pairs in an array whose sum is equal to k (solution)
• How to find the largest and smallest number in an array without sorting? (solution)
• How to find one missing number in a sorted array? (solution)
• How to remove an element from an array in Java? (solution)
• How do find the top 2 numbers from a given array? (solution)
• Top 30 linked list coding interview questions (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms Books Every Programmer Should Read (books)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)
• How to sort an array using bubble sort in Java? (solution)
• How to find duplicates from an unsorted array in Java? (solution)
• How to remove duplicates from an array in Java? (solution)

P. S. — If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Data Structure in Java free course on Udemy. It’s completely free and all you need to do is create a free Udemy account to enroll in this course.

P. P. S. — If you want more of such questions from tech interviews, please see Cracking the Coding Interview 6th Edition, which contains over 190 coding questions from different software companies, startups, investment banks, and service-based companies.

Источник

Руководство по алгоритму сортировки на месте работает с реализацией Java

В этом учебнике мы объясним, как работает алгоритм сортировки на месте.

2. Алгоритмы на месте

Алгоритмы на месте — это алгоритмы, которые не нуждаются в вспомогательной структуре данных для преобразования входных данных. В принципе, это означает, что алгоритм не использует дополнительное пространство для ввода манипуляции. Он практически переопределяет вход с выходом.

Однако на самом деле алгоритм может потребовать небольшого и неконтуятного дополнительного пространства для вспомогательных переменных. Сложность этого пространства в большинстве случаев O (журнал n) , хотя иногда разрешается что-либо меньшее, чем линейное.

3. Псевдокод

Давайте теперь посмотрим какой-нибудь псевдокод и сравним алгоритм на месте с неместо него.

Мы предположим, что мы хотим обратить вспять массив n Числа.

3.1. Алгоритм на месте

Если мы подумаем о проблеме, мы увидим, что у нас есть входной массив и обратный массив в качестве вывода. В конце концов, нам на самом деле не нужен наш оригинальный массив, только обратный.

Тогда почему бы нам не переписать вход вместо того, чтобы перейти его значения к совершенно новому массиву, так как это может выглядеть как наиболее очевидный метод? Чтобы сделать это, Нам понадобится только одна дополнительная переменная временно хранить значения, с которые мы в настоящее время работаем:

reversInPlace(array A[n]) for i from 0 to n/2 temp = A[i] A[i] = A[n - 1 - i] A[n - 1 - i] = temp

Примечательно отметить, что независимо от того, насколько велик массив, дополнительное пространство, которое нам нужно, всегда будет O(1) в этом случае.

Иллюстрация показывает, что нам нужно меньше шагов, чем в предыдущем случае:

3.2. Алгоритм вне места

С другой стороны, мы также можем сделать это в довольно простой, более очевидным образом. Мы можем создать новый массив того же размера, скопировать значения из исходного в соответствующем порядке, а затем удалить исходный массив:

reverseOutOfPlace(array A[n]) create new array B[n] for i from 0 to n - 1 B[i] = A[i] delete A return B

Хотя это будет делать то, что мы хотели, это не достаточно эффективно. У нас О(н) дополнительное пространство, необходимое так как у нас есть два массива, чтобы манипулировать . Кроме того, создание и удаление нового массива обычно является медленной операцией.

Давайте посмотрим на иллюстрацию процесса:

4. Реализация Java

Давайте теперь посмотрим, как мы можем реализовать в Java то, что мы узнали в предыдущем разделе.

Во-первых, мы реализуем алгоритм на месте:

public static int[] reverseInPlace(int A[]) < int n = A.length; for (int i = 0; i < n / 2; i++) < int temp = A[i]; A[i] = A[n - 1 - i]; A[n - 1 - i] = temp; >return A; >

Мы можем легко проверить, что это работает, как ожидалось:

@Test public void givenArray_whenInPlaceSort_thenReversed() < int[] input = ; int[] expected = ; assertArrayEquals("the two arrays are not equal", expected, InOutSort.reverseInPlace(input)); >

Во-вторых, давайте проверим вне места реализации алгоритма:

public static int[] reverseOutOfPlace(int A[]) < int n = A.length; int[] B = new int[n]; for (int i = 0; i < n; i++) < B[n - i - 1] = A[i]; >return B; >

@Test public void givenArray_whenOutOfPlaceSort_thenReversed() < int[] input = ; int[] expected = ; assertArrayEquals("the two arrays are not equal", expected, InOutSort.reverseOutOfPlace(input)); >

5. Примеры

Есть много алгоритмов сортировки, которые используют на месте подход. Некоторые из них являются сортировка вставки , пузырь рода , куча рода , quicksort , и оболочки рода, и вы можете узнать больше о них и проверить свои реализации Java.

Кроме того, мы должны упомянуть гребень рода и heapsort. Все они имеют космическую сложность O (журнал n) .

Было бы также полезно узнать больше о теории Big-O Notation , а также проверить некоторые практические примеры Java о сложности алгоритма .

6. Заключение

В этой статье мы описали так называемые на месте алгоритмы, проиллюстрировали, как они работают с использованием псевдокода и несколько примеров, перечислили несколько алгоритмов, которые работают по этому принципу, и, наконец, реализовали основные примеры в Java.

Как обычно, весь код можно найти более на GitHub .

Источник