ObjectOne > Java > Массив — Инвертируем массив в Java 3 способа

Массив — Инвертируем массив в Java 3 способа

Распечатка работы программы. Пример №1

Код программы. Пример №1

Метод не разворачивает массив. Сначала он меняет местами крайние, приближаясь к середине, а после середины по-новой. Зеркалит относительно центра. Пример с временным массивчиком.

Распечатка работы программы. Пример №2

Код программы. Пример №2

Один из популярнейших вопросов

Один из популярнейших вопросов на интервью для 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. Так что в случае четного количества элементов средние элементы поменяются местами, а в случае нечетного средний элемент останется на месте.

 

Источник qa7.ru

Код программы. Пример №3


Количество просмотров: 2 350

| Категория: Java
| Тэги: