Обращение части массива (или любой другой структуры данных) - PullRequest
Новая
       2

Обращение части массива (или любой другой структуры данных)

0 голосов
/ 01 декабря 2011

Я хочу перевернуть массив (или любую другую структуру данных), но поскольку эта операция будет выполняться над массивом n раз, я ищу наилучшее возможное решение, у меня есть отсортированный массив, который получается в О (nlgn) время, я начинаю искать первый элемент в отсортированном массиве внутри несортированного массива (что равно нахождению наименьшего ключа в несортированном массиве), затем я обращаю массив от начала к индексу этого значения, затем я делаю то же самое для остальных, нахожу индекс второго наименьшего значения и снова обращаю массив, от второго индекса до конца массива и так далее:
например, рассмотрим этот массив: 

*‫2 6 (*1*) 5 4 *3‬  // array is reversed from its 0th index to the 3rd index (0 based)     
1 *5* 4 3 6 (*2*)  // array is reversed from its 1st index (0 based ) to the 5th index   
1 2 *6* *3* 4 5    // and ...  
1 2 3 *6* *4* 5  
1 2 3 4 *6* *5*  
1 2 3 4 5 6

ну, мне нужно отсортировать массив, чтобы получить значения, которые он ищет в несортированном массиве, это займет время o (nlgn), а выполнение приведенного выше алгоритма - o (n ^ 2), любое идея сделать это быстрее, чтобы быть сделано в o (nlgn) время? поэтому вопрос состоит в обращении подмассива массива в порядке наименьшего времени, потому что это много раз делается в массивах большого размера. (Я могу получить индексы i и j (которые являются первым и последним индексом подмассива) за O (n) время, потому что у меня есть отсортированный массив, и я просто посмотрю числа в несортированном массиве), так что я ищем лучший порядок времени для обращения массива от его i-го индекса к его j-му индексу.
заранее спасибо

Ответы [ 3 ]

0 голосов
/ 01 декабря 2011

Похоже, очень простой ответ на сложный вопрос, так что, может быть, я что-то упустил.Если вы ищете эффективный способ перевернуть часть массива, то что-то вроде следующего должно работать.Конечно, вы можете легко сделать его универсальным. 

// endIndex and startIndex are inclusive here
int half = startIndex + ((endIndex + 1) - startIndex) / 2;
int endCount = endIndex;
for (int startCount = startIndex; startCount < half; startCount++) {
    int store = array[startCount];
    array[startCount] = array[endCount];
    array[endCount] = store;
    endCount--;
}

Похоже, что остальная часть вашего кода будет намного сложнее, чем эта.Не уверен, что здесь O (), потому что он не выполняет сравнения, которые традиционно являются мерой, но выполняет 1,5 x N присваиваний для обращения массива.Я не вижу способа сделать это быстрее.

0 голосов
/ 02 декабря 2011

А вот и решение O (n) (думаю, прочитать ваше описание было сложно). Это структура данных, которая позволяет 1) обратить подмассив в O (1), 2) получить значение из массива в O (r), где r - количество выполненных обращений, 3) найти индекс элемента в O (n), где n - длина списка.

Просто сохраните наш массив как обычно и получите список из ReversedRange(imin, imax) элементов. Обратить часть массива так же просто, как вставить другой элемент в этом списке.

Всякий раз, когда вам нужно получить значение из модифицированного массива по индексу i, вы просматриваете все ReversedRange, для которых imin <= i <= imax, и вычисляете индекс j, который соответствует исходному индексу массива. Вам нужно проверить r реверсы, так что это O (r).

Чтобы получить индекс i значения v, просмотрите исходный массив и найдите индекс j. Совершено за O (n). Выполните тот же обход ReversedRange s, только в противоположном направлении, чтобы вычислить i. Совершено за O (r), всего O (n + r), что равно O (n).

* * Пример тысячи тридцать один * ** +1032 +1033 *

Рассмотрим следующий список: 0 1 2 3 4 5 6 7 8 9. Теперь допустим, что мы изменили индексы формы списка от 1 до 6, а затем от 0 до 5. Итак имеем: 

I    0 1 2 3 4 5 6 7 8 9
       |         |
II   0 6 5 4 3 2 1 7 8 9
     |         |
III  2 3 4 5 6 0 1 7 8 9

Нет, давайте сопоставим индекс i = 2 с исходным массивом. Из графика мы видим, что мы должны получить III(2) = 4

1) since i = 2 is in [0, 5] we calculate
    i <- 5 - (i - 0) = 5 - 2 = 3
2) since i = 3 is in [1, 6] we calculate
    i <- 6 - (i - 1) = 6 - 2 = 4
3) there are no more ranges, we are done with result 4!
0 голосов
/ 01 декабря 2011

(возможно) тяжелая память ...

Почему бы вам не сохранить две коллекции. Пройдите оригинальную коллекцию, пока не найдете свою обратную точку. Затем перейдите назад с помощью итератора или индексации, если он у вас есть (ArrayList), добавив каждый элемент в новую коллекцию. Затем объедините две коллекции (перевернутая часть и предыдущая нетронутая часть). Повторите это, пока не закончите.

...