用于M位置的圆移N大小数组的最快算法

Question

M位置的圆移位阵列的最快算法是什么？
例如,[3 4 5 2 3 1 4]班次M = 2个位置应该是[1 4 3 4 5 2 3].

非常感谢.

Answer 1

如果你想要O(n)时间并且没有额外的内存使用(因为指定了数组),请使用Jon Bentley的书"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的元素顺序颠倒过来.

Answer 2

这只是一个代表问题.将当前索引保持为整数变量,并且在遍历数组时使用模运算符来知道何时换行.然后,移位仅改变当前索引的值,将其包围在数组的大小周围.这当然是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;
}

Answer 3

最优解决方案

问题要求最快.反转三次是最简单的,但每个元素移动两次,需要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倍.参考:http://www.geeksforgeeks.org/array-rotation/

Answer 4

用指针设置它,几乎没有时间.每个元素指向下一个,而"最后一个"(没有最后一个;毕竟,你说它是圆形的)指向第一个.一个指向"开始"(第一个元素)的指针,也许是一个长度,你有你的数组.现在,为了完成你的转变,你只需沿着圆圈走开始指针.

要求一个好的算法,你会得到明智的想法.要求最快,你得到奇怪的想法!