1 2 3 4 5 |
Введите размерность массива: 14 Первоначальные элементы массива: 14 14 0 7 -2 2 -1 -2 -4 -1 12 -1 4 10 Переработонные элементы массива: 10 4 -1 12 -1 -4 -2 -1 2 -2 7 0 14 14 Ну точно убеждаемся что мы инвертировали все элементы: [10, 4, -1, 12, -1, -4, -2, -1, 2, -2, 7, 0, 14, 14] |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
import java.util.Arrays; import java.util.Scanner; public class testArray { static void returnReversArray(int[] arr){ int temp; for (int i = arr.length-1, j = 0; i >=arr.length/2 ; i--,j++) { temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Введите размерность массива: "); int sizeArr = in.nextInt(); int[] arr = new int[sizeArr]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random()*20-5); } System.out.print("Первоначальные элементы массива: "); for(int key : arr){ System.out.print(key+" "); } System.out.print("\nПереработонные элементы массива: "); returnReversArray(arr); for(int key : arr){ System.out.print(key+" "); } System.out.print("\nНу точно убеждаемся что мы инвертировали все элементы: "); System.out.println("\n"+Arrays.toString(arr)); } } |
Метод не разворачивает массив. Сначала он меняет местами крайние, приближаясь к середине, а после середины по-новой. Зеркалит относительно центра. Пример с временным массивчиком.
1 2 3 4 5 |
Введите размерность массива: 20 Первоначальные элементы массива: -3 12 2 0 -4 7 9 -1 -4 11 14 1 0 13 -4 0 10 11 14 8 Переработонные элементы массива: 8 14 11 10 0 -4 13 0 1 14 11 -4 -1 9 7 -4 0 2 12 -3 Возвратили и обработали массив: 8 14 11 10 0 -4 13 0 1 14 11 -4 -1 9 7 -4 0 2 12 -3 [8, 14, 11, 10, 0, -4, 13, 0, 1, 14, 11, -4, -1, 9, 7, -4, 0, 2, 12, -3] |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import java.util.Arrays; import java.util.Scanner; public class testArray { static int[] returnReversArray(int[] arr) { int j = 0; int[] res = new int[arr.length]; //Создаём временный массивчик for (int i = arr.length - 1; i >= 0; i--, j++) { res[j] = arr[i]; System.out.print(res[j] + " "); } return res; } public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Введите размерность массива: "); int sizeArr = in.nextInt(); int[] arr = new int[sizeArr]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random()*20-5); } System.out.print("Первоначальные элементы массива: "); for(int key : arr){ System.out.print(key+" "); } System.out.print("\nПереработонные элементы массива: "); int[] arr2 = returnReversArray(arr); System.out.print("\nВозвратили и обработали массив: "); for(int key : arr2){ System.out.print(key+" "); } System.out.println("\n"+Arrays.toString(arr2)); } } |
Один из популярнейших вопросов на интервью для java-девелопера это просьба перевернуть массив. Это очень похоже на вопрос из прошлой статьи, про переворачивание строки, но немного про другое. Вопрос не выглядит сложным, все что нужно сделать это создать новый массив такого же размера, перебрать исходный массив от конца до нажала заполняя новый. Все, готово. Но нет, мы же создали дополнительный массив того же размера, что и исходный, что усложняет наше решение O(n). Мы не сможем использовать наше решение, если размер массива очень большой (например 10 млн элементов), а размер heap небольшой. Что мы можем тут сделать? Как улучшить наше решение? Можем ли мы перевернуть массив не создавая дополнительный буффер? Для нашей задачи предположим, что у нас массив из integer (вообще на интервью хорошая практика задавать правильные вопросы в правильных местах, как говорят знающие люди это черта хорошего программиста). Ключевое тут понять, что вам нужно перевернуть исходный массив, мы не можем использовать другой массив, но использовать одну две дополнительные переменные, вполне допустимо. Так же недопустимо использование сторонних библиотек или Java API которые могут сделать эту работу за нас, а также методов класса java.util.Arrays, за исключением Arrays.toString() чтобы выводить массивы. Когда наши требования выяснены приступим к решению задачи.
Первое что приходит в голову это перебрать все элементы массива и поменять их местами. Первый элемент и последний, второй элемент с предпоследним, и т.д. В этом случае все элементы массивы будут перевернуты без использования дополнительного буффера. Ключевая вещь здесь, которую нужно держать в голове это только что нам нужно менять местами элементы до того момента как мы достигнем середины массива, иначе мы получим тот же самый массив. Возникает закономерный вопрос, а что если массив имеет четное количество элементов? В этом случае в середине массива будут два элемента, и нам нужно поменять их местами, поэтому наше условие перебора будет содержать выражение index <= middle а не index < middle. Середина тут ничто иное как length/2. Помните что мы будем использовать оператор / что означает в случае если length равно 8, вернет нам 4, а в случае если length равно 7, вернет нам 3. Так что в случае четного количества элементов средние элементы поменяются местами, а в случае нечетного средний элемент останется на месте.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
import java.util.Arrays; /** * Java Program to demonstrate how to reverse an array in place. */ public class ArrayReversalDemo { public static void main(String[] args) { int[] numbers = {1, 2, 3, 4, 5, 6, 7}; reverse(numbers); } /** * reverse the given array in place * @param input */ public static void reverse(int[] input) { System.out.println("original array : " + Arrays.toString(input)); // handling null, empty and one element array if (input == null || input.length <= 1) { return; } for (int i = 0; i < input.length / 2; i++) { int temp = input[i]; // swap numbers input[i] = input[input.length - 1 - i]; input[input.length - 1 - i] = temp; } System.out.println("reversed array : " + Arrays.toString(input)); } } |
| Категория: Java
| Тэги: массивы