Оптимальное решение
Вопрос задан быстрее всех. Реверсировать три раза проще, но каждый элемент перемещается ровно дважды, занимает 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, мы можем сдвинуть круг с тремя циклами:
tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;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 раза.
Ссылка: http://www.geeksforgeeks.org/array-rotation/