#java #arrays #algorithm
#java #массивы #алгоритм
Вопрос:
Я пишу программу на Java, в которой мне нужно перемещать элементы массива, и она должна выполнять как можно меньшее количество операций, поскольку она находится внутри двойного цикла, и я работаю с длиной массива в диапазоне до 10 ^ 8.
Пример: A = {1,2,3,4,5,6} Результат : A = {2,3,4,5,6,1} в первый раз, A = {3,4,5,6,1,2} во второй раз и так далее..
Пожалуйста, не стесняйтесь предлагать любую другую структуру данных или любые модификации массива!! Спасибо вам, ребята!! 😀
Ответ №1:
Самый простой способ добиться этого эффекта — создать «циклический массив»; то есть вместо перемещения содержимого массива вы можете просто сохранить индекс, который отмечает начало массива.
Чтобы получить элемент с индексом i, вы затем выполняете:
Type item = arr[(offset i) % arr.length];
Таким образом, вы получаете те же свойства, что и у массива, и можете выполнять любое вращение в O (1).
Чтобы сделать это менее сложным в использовании, вы могли бы создать простой класс-оболочку, который просто оборачивает массив, позволяя легко поворачивать с помощью этого метода. Таким образом, код может выглядеть чистым, в то время как вы получаете эффективную ротацию.
Комментарии:
1. Как я уже говорил ранее, я имею дело с большим контентом, работающим в нескольких циклах, и это делает код более сложным. Ваша идея потрясающая, но не подходит для моего случая!!! Tak ven
2. Вы могли бы создать класс, который обтекает его, делая прозрачным для пользователя.
Ответ №2:
Для достижения сложности O (1) вы могли бы…
- используйте связанный список
- оберните свой массив классом, который хранит начальную позицию и позволяет получить доступ к массиву через «виртуальные» индексы (wrapped.acces(i) => array[(start i) % array.length]
- «удвойте» свой массив и нарежьте его соответствующим образом (чтобы вам не пришлось изменять окружающий код)
В противном случае, если вы хотите придерживаться своей структуры данных, вам нужно заплатить O (n), несмотря ни на что.
Я бы выбрал (2), потому что это быстрее как для шаблонов произвольного доступа, так и для шаблонов линейного доступа (массивы имеют лучшую локальность данных O (1) сложность произвольного доступа по сравнению с O (n) связанных списков).
Комментарии:
1. @Mojo_Jojo: но имейте в виду, что итерация по связанному списку выполняется медленнее, чем итерация по массиву (наихудшая локализация данных), и это не подходит, если вам нужно получить к нему случайный доступ.
Ответ №3:
Используйте Collections.rotate(Arrays.asList(myArray), myDistance) .
Комментарии:
1. Каково количество операций, задействованных в нем, приятель? Выполняет ли это работу за меньшее время, чем обычная функция, которую может написать любой?
2. Алгоритм, используемый
Collections.rotate, описан в Javadoc. Список, который является результатомArrays.asListреализацииRandomAccess, поэтому результат действительно будет таким быстрым, как вы могли бы сделать, написав свой собственный алгоритм.3. Я должен сделать оговорку по этому поводу. Реализация, использующая методы Arrays.copyOf, вероятно, была бы быстрее на практике.
Ответ №4:
Если вы не женаты на идее использования массивов, то вы могли бы воспользоваться методом Collections.rotate().
List<Integer> list = new ArrayList<Integer>();
for (int i = 1; i <= 6; i ) {
list.add(i-1, new Integer(i));
}
int j = 0;
while (j < 100) {
Collections.rotate(list, -1);
System.out.print("{");
for (Integer integer : list) {
System.out.print(integer ", ");
}
System.out.println("}");
}
Комментарии:
1. Вы могли бы напрямую распечатать список, нет необходимости использовать цикл for для его печати.
Ответ №5:
Почему вам нужно поворачивать таблицу?
Представьте, что таблица представляет собой круг, и после этого вы можете ходить вот так:
Object object = array[(offset i) % array.length];
Это дает вам O (1) на любом шаге доступа или поворота;
Ответ №6:
Для этого вы можете использовать простой список. Если вы часто выполняете это перемещение, лучшим выбором будет очередь. Дело в том, что массив на самом деле не меняется, вы просто начинаете чтение с позиции x, а затем продолжаете чтение с начала элементов array length (длина массива)-x. Это самый быстрый вариант.