Самый быстрый алгоритм для массива размера круга N для M позиции

Каков самый быстрый алгоритм для массива смещения кругов для m позиций?
Например, [3 4 5 2 3 1 4] сдвиг m = 2 положения должны быть [1 4 3 4 5 2 3]

большое спасибо

Если вы хотите время O (n) и дополнительное использование памяти (поскольку массив был указан), используйте алгоритм из книги Джона Бентли «Programming Pearls 2nd Edition». Он меняет все элементы дважды. Не так быстро, как использование связанных списков, но использует меньше памяти и концептуально просто.

shiftArray( theArray, M ): size = len( theArray ) assert( size > M ) reverseArray( theArray, 0, size - 1 ) reverseArray( theArray, 0, M - 1 ) reverseArray( theArray, M, size - 1 ) 

reverseArray (anArray, startIndex, endIndex) отменяет порядок элементов от startIndex до endIndex включительно.

Это всего лишь вопрос представительства. Сохраняйте текущий индекс как целочисленную переменную, и при обходе массива используйте оператор modulo, чтобы знать, когда его нужно обернуть. Shifting только меняет значение текущего индекса, обертывая его вокруг размера массива. Это, конечно, O (1).

Например:

 int index = 0; Array a = new Array[SIZE]; get_next_element() { index = (index + 1) % SIZE; return a[index]; } shift(int how_many) { index = (index+how_many) % SIZE; } 

Оптимальное решение

Вопрос поставлен быстрее. Реверсирование три раза проще, но каждый элемент выполняет ровно два раза, занимает O (N) время и O (1). Можно окружить сдвиг массива, перемещающего каждый элемент ровно один раз и в O (N) время и O (1) пробел.

идея

Мы можем окружать сдвиг массивом длины N=9 на M=1 с одним циклом:

 tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp; 

А если N=9 , M=3 мы можем сдвинуть круг с тремя циклами:

  1. tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;
  2. tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;
  3. tmp = arr[2]; arr[2] = arr[5]; arr[5] = tmp;

Обратите внимание, что каждый элемент считывается один раз и записывается один раз.

Схема сдвига N=9, M=3

Диаграмма смещения цикла

Первый цикл показывает черным с цифрами, указывающими порядок операций. Второй и третий циклы отображаются серым цветом.

Количество требуемых циклов – это Величайший общий делитель (GCD) из N и M Если GCD равен 3, мы начинаем цикл в каждом из {0,1,2} . Вычисление GCD происходит быстро с помощью бинарного алгоритма GCD .

Пример кода:

 // n is length(arr) // shift is how many place to cycle shift left void cycle_shift_left(int arr[], int n, int shift) { int i, j, k, tmp; if(n <= 1 || shift == 0) return; shift = shift % n; // make sure shift isn't >n int gcd = calc_GCD(n, shift); for(i = 0; i < gcd; i++) { // start cycle at i tmp = arr[i]; for(j = i; 1; j = k) { k = j+shift; if(k >= n) k -= n; // wrap around if we go outside array if(k == i) break; // end of cycle arr[j] = arr[k]; } arr[j] = tmp; } } 

Код в C для любого типа массива:

 // circle shift an array left (towards index zero) // - ptr array to shift // - n number of elements // - es size of elements in bytes // - shift number of places to shift left void array_cycle_left(void *_ptr, size_t n, size_t es, size_t shift) { char *ptr = (char*)_ptr; if(n <= 1 || !shift) return; // cannot mod by zero shift = shift % n; // shift cannot be greater than n // Using GCD size_t i, j, k, gcd = calc_GCD(n, shift); char tmp[es]; // i is initial starting position // Copy from k -> j, stop if k == i, since arr[i] already overwritten for(i = 0; i < gcd; i++) { memcpy(tmp, ptr+es*i, es); // tmp = arr[i] for(j = i; 1; j = k) { k = j+shift; if(k >= n) k -= n; if(k == i) break; memcpy(ptr+es*j, ptr+es*k, es); // arr[j] = arr[k]; } memcpy(ptr+es*j, tmp, es); // arr[j] = tmp; } } // cycle right shifts away from zero void array_cycle_right(void *_ptr, size_t n, size_t es, size_t shift) { if(!n || !shift) return; // cannot mod by zero shift = shift % n; // shift cannot be greater than n // cycle right by `s` is equivalent to cycle left by `n - s` array_cycle_left(_ptr, n, es, n - shift); } // Get Greatest Common Divisor using binary GCD algorithm // http://en.wikipedia.org/wiki/Binary_GCD_algorithm unsigned int calc_GCD(unsigned int a, unsigned int b) { unsigned int shift, tmp; if(a == 0) return b; if(b == 0) return a; // Find power of two divisor for(shift = 0; ((a | b) & 1) == 0; shift++) { a >>= 1; b >>= 1; } // Remove remaining factors of two from a - they are not common while((a & 1) == 0) a >>= 1; do { // Remove remaining factors of two from b - they are not common while((b & 1) == 0) b >>= 1; if(a > b) { tmp = a; a = b; b = tmp; } // swap a,b b = b - a; } while(b != 0); return a << shift; } 

Редактирование . Этот алгоритм может также иметь лучшую производительность по сравнению с изменением массива (когда N велико, а M - небольшим) из-за локальности кэша, поскольку мы чередуем массив по малым шагам.

Заключительное примечание: если ваш массив мал, тройной обратный порядок прост. Если у вас большой массив, стоит накладные расходы на разработку GCD, чтобы уменьшить количество ходов в 2 раза. Ref: http://www.geeksforgeeks.org/array-rotation/

Настройте его с помощью указателей, и это займет почти нет времени. Каждый элемент указывает на следующий, а «последний» (нет последнего, ведь вы сказали, что он круговой) указывает на первое. Один указатель на «начало» (первый элемент) и, возможно, длину, и у вас есть массив. Теперь, чтобы сделать вашу смену, вы просто пропустите указатель начала по кругу.

Попросите хороший алгоритм, и вы получите разумные идеи. Спросите быстрее , и вы получите странные идеи!

Этот алгоритм работает в O (n) времени и O (1) пространстве. Идея состоит в том, чтобы проследить каждую циклическую группу в сдвиге (пронумерованную переменной nextGroup ).

 var shiftLeft = function(list, m) { var from = 0; var val = list[from]; var nextGroup = 1; for(var i = 0; i < list.length; i++) { var to = ((from - m) + list.length) % list.length; if(to == from) break; var temp = list[to]; list[to] = val; from = to; val = temp; if(from < nextGroup) { from = nextGroup++; val = list[from]; } } return list; } 

В зависимости от используемой структуры данных вы можете сделать это в O (1). Я думаю, что самый быстрый способ – держать массив в виде связанного списка и иметь хеш-таблицу, которая может переводить между «индексом» в массиве на «указатель» на запись. Таким образом, вы можете найти соответствующие главы и хвосты в O (1) и выполнить повторное соединение в O (1) (и обновить hash-таблицу после переключения в O (1)). Это, конечно, было бы очень «грязным» решением, но если все, что вас интересует, это скорость сдвига, что будет делать (за счет более длинной вставки и поиска в массиве, но он все равно останется O ( 1))

Если у вас есть данные в чистом массиве, я не думаю, что вы можете избежать O (n).

Кодируя, это зависит от того, какой язык вы используете.

Например, в Python вы можете «нарезать» его (предположим, что n – это размер сдвига):

 result = original[-n:]+original[:-n] 

(Я знаю, что hash-поиск теоретически не O (1), но мы здесь практические и не теоретические, по крайней мере, я надеюсь …)

C arrayShiftRight. Если сдвиг отрицательный, функция сдвигает массив влево. Он оптимизирован для меньшего использования памяти. Время работы – O (n).

 void arrayShiftRight(int array[], int size, int shift) { int len; //cut extra shift shift %= size; //if shift is less then 0 - redirect shifting left if ( shift < 0 ) { shift += size; } len = size - shift; //choosing the algorithm which needs less memory if ( shift < len ) { //creating temporary array int tmpArray[shift]; //filling tmp array for ( int i = 0, j = len; i < shift; i++, j++ ) { tmpArray[i] = array[j]; } //shifting array for ( int i = size - 1, j = i - shift; j >= 0; i--, j-- ) { array[i] = array[j]; } //inserting lost values from tmp array for ( int i = 0; i < shift; i++ ) { array[i] = tmpArray[i]; } } else { //creating temporary array int tmpArray[len]; //filling tmp array for ( int i = 0; i < len; i++ ) { tmpArray[i] = array[i]; } //shifting array for ( int i = 0, j = len; j < size; i++, j++ ) { array[i] = array[j]; } //inserting lost values from tmp array for ( int i = shift, j = 0; i < size; i++, j++ ) { array[i] = tmpArray[j]; } } } 
 def shift(nelements, k): result = [] length = len(nelements) start = (length - k) % length for i in range(length): result.append(nelements[(start + i) % length]) return result 

Этот код хорошо работает даже при отрицательном сдвиге k

Это должно работать для смещения кругового движения: Input: {1, 2, 3, 5, 6, 7, 8}; Выходное значение присутствует в массиве после forloops: {8,7,1,2,3,5,6,8,7}

  class Program { static void Main(string[] args) { int[] array = { 1, 2, 3, 5, 6, 7, 8 }; int index = 2; int[] tempArray = new int[array.Length]; array.CopyTo(tempArray, 0); for (int i = 0; i < array.Length - index; i++) { array[index + i] = tempArray[i]; } for (int i = 0; i < index; i++) { array[i] = tempArray[array.Length -1 - i]; } } } 

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

 int[] a = {1,2,3,4,5,6}; int k = 2; int[] queries = {2,3}; int[] temp = new int[a.length]; for (int i = 0; i 

Храните два индекса в массиве, один индекс начинается с начала массива до конца массива. Другой индекс начинается с M-й позиции от последней и циклически проходит через последние M элементов сколько угодно раз. Принимает O (n) в любое время. Больше места не требуется.

 circleArray(Elements,M){ int size=size-of(Elements); //first index int i1=0; assert(size>M) //second index starting from mth position from the last int i2=size-M; //until first index reaches the end while(i1 в circleArray(Elements,M){ int size=size-of(Elements); //first index int i1=0; assert(size>M) //second index starting from mth position from the last int i2=size-M; //until first index reaches the end while(i1 

Смотрите это, если вас интересует реализация Java:

Программирование жемчуга: круговая левая / правая операция переключения

 static int [] shift(int arr[], int index, int k, int rem) { if(k <= 0 || arr == null || arr.length == 0 || rem == 0 || index >= arr.length) { return arr; } int temp = arr[index]; arr = shift(arr, (index+k) % arr.length, k, rem - 1); arr[(index+k) % arr.length] = temp; return arr; } 

Пример Ruby:

 def move_cyclic2 array, move_cnt move_cnt = array.length - move_cnt % array.length if !(move_cnt == 0 || move_cnt == array.length) array.replace( array[move_cnt..-1] + array[0...move_cnt] ) end end 

Теоретически, самый быстрый из них – это цикл:

 if (begin != middle && middle != end) { for (i = middle; ; ) { swap(arr[begin++], arr[i++]); if (begin == middle && i == end) { break; } if (begin == middle) { middle = i; } else if (i == end) { i = middle; } } } 

На практике вы должны просмотреть его и посмотреть.

Вот еще один (C ++):

 void shift_vec(vector& v, size_t a) { size_t max_s = v.size() / a; for( size_t s = 1; s < max_s; ++s ) for( size_t i = 0; i < a; ++i ) swap( v[i], v[s*a+i] ); for( size_t i = 0; i < a; ++i ) swap( v[i], v[(max_s*a+i) % v.size()] ); } 

Конечно, это не так элегантно, как знаменитое обратное трехрежимное решение, но в зависимости от машины оно может быть аналогичным быстро .

circleArray имеет некоторые ошибки и не работает во всех случаях!

Цикл должен продолжаться, while i1 < i2 NOT i1 < last - 1 .

 void Shift(int* _array, int _size, int _moves) { _moves = _size - _moves; int i2 = _moves; int i1 = -1; while(++i1 < i2) { int tmp = _array[i2]; _array[i2] = _array[i1]; _array[i1] = tmp; if(++i2 == _size) i2 = _moves; } } 

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

Взгляните сюда .

 #include  #include  #include  using namespace std; struct VeryElaboratedDataType { int a; int b; }; namespace amsoft { namespace inutils { enum EShiftDirection { Left, Right }; template  void infernalShift(T infernalArray[],int positions,EShiftDirection direction = EShiftDirection::Right) { //assert the dudes assert(len > 0 && "what dude?"); assert(positions >= 0 && "what dude?"); if(positions > 0) { ++positions; //let's make it fit the range positions %= len; //if y want to live as a forcio, i'l get y change direction by force if(!direction) { positions = len - positions; } // here I prepare a fine block of raw memory... allocate once per thread static unsigned char WORK_BUFFER[len * sizeof(T)]; // std::memset (WORK_BUFFER,0,len * sizeof(T)); // clean or not clean?, well // Hamlet is a prince, a prince does not clean //copy the first chunk of data to the 0 position std::memcpy(WORK_BUFFER,reinterpret_cast(infernalArray) + (positions)*sizeof(T),(len - positions)*sizeof(T)); //copy the second chunk of data to the len - positions position std::memcpy(WORK_BUFFER+(len - positions)*sizeof(T),reinterpret_cast(infernalArray),positions * sizeof(T)); //now bulk copy back to original one std::memcpy(reinterpret_cast(infernalArray),WORK_BUFFER,len * sizeof(T)); } } template  void printArray(T infernalArrayPrintable[],int len) { for(int i=0;i void printArray(VeryElaboratedDataType infernalArrayPrintable[],int len) { for(int i=0;i(myInfernalArray,4); amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int)); amsoft::inutils::infernalShift(myInfernalArray,4,amsoft::inutils::EShiftDirection::Left); amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int)); amsoft::inutils::infernalShift(myInfernalArray,10); amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int)); amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)); amsoft::inutils::infernalShift(myInfernalArrayV,4); amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)); amsoft::inutils::infernalShift(myInfernalArrayV,4,amsoft::inutils::EShiftDirection::Left); amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)); amsoft::inutils::infernalShift(myInfernalArrayV,10); amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)); return 0; } 

Этот метод будет выполнять эту работу:

 public static int[] solution1(int[] A, int K) { int temp[] = new int[A.length]; int count = 0; int orignalItration = (K < A.length) ? K :(K%A.length); for (int i = orignalItration; i < A.length; i++) { temp[i] = A[count++]; } for (int i = 0; i < orignalItration; i++) { temp[i] = A[count++]; } return temp; } 

Вот простая и эффективная общая функция rotate на C ++, менее 10 строк.

который выдается из моего ответа по другому вопросу. Как повернуть массив?

 #include  #include  // same logic with STL implementation, but simpler, since no return value needed. template  void rotate_by_gcd_like_swap(Iterator first, Iterator mid, Iterator last) { if (first == mid) return; Iterator old = mid; for (; mid != last;) { std::iter_swap(first, mid); ++first, ++mid; if (first == old) old = mid; // left half exhausted else if (mid == last) mid = old; } } int main() { using std::cout; std::vector v {0,1,2,3,4,5,6,7,8,9}; cout << "before rotate: "; for (auto x: v) cout << x << ' '; cout << '\n'; int k = 7; rotate_by_gcd_like_swap(v.begin(), v.begin() + k, v.end()); cout << " after rotate: "; for (auto x: v) cout << x << ' '; cout << '\n'; cout << "sz = " << v.size() << ", k = " << k << '\n'; } 

Подобно @IsaacTurner, а не тому, что изящно из-за ненужного копирования, но реализация довольно короткая.

Идея – заменить элемент A на индекс 0 с элементом B, который находится на пункте назначения A. Теперь B является первым. Поменяйте его на элемент C, который находится в пункте назначения B. Продолжайте, пока пункт назначения не будет равен 0.

Если наибольший общий делитель не равен 1, вы еще не закончили – вам нужно продолжить замену, но теперь используйте индекс 1 в начальной и конечной точке.

Продолжайте, пока ваша начальная позиция не будет gcd.

 int gcd(int a, int b) => b == 0 ? a : gcd(b, a % b); public int[] solution(int[] A, int K) { for (var i = 0; i < gcd(A.Length, K); i++) { for (var j = i; j < A.Length - 1; j++) { var destIndex = ((ji) * K + K + i) % A.Length; if (destIndex == i) break; var destValue = A[destIndex]; A[destIndex] = A[i]; A[i] = destValue; } } return A; } 

Вот мое решение на Java, которое получило 100% -ную оценку задачи и 100% -ную правильность в Codility:

 class Solution { public int[] solution(int[] A, int K) { // write your code in Java SE 8 if (A.length > 0) { int[] arr = new int[A.length]; if (K > A.length) K = K % A.length; for (int i=0; i 

Обратите внимание, что, несмотря на просмотр двух циклов, итерация по всему массиву выполняется только один раз.

Версия Swift 4 для перемещения массива влево.

 func rotLeft(a: [Int], d: Int) -> [Int] { var result = a func reverse(start: Int, end: Int) { var start = start var end = end while start < end { result.swapAt(start, end) start += 1 end -= 1 } } let lenght = a.count reverse(start: 0, end: lenght - 1) reverse(start: lenght - d, end: lenght - 1) reverse(start: 0, end: lenght - d - 1) return result } 

Например, если входной массив равен a = [1, 2, 3, 4, 5] , а сдвиг влево сдвиг равен d = 4 , тогда результат будет [5, 1, 2, 3, 4]

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