快速算法：将大小为N的数组进行圆形移位，移动M个位置。

Question

什么是移位M个位置的圆形数组的最快算法？
例如，[3 4 5 2 3 1 4] 移动 M = 2 个位置应该是 [1 4 3 4 5 2 3]。

非常感谢。

- Arsen Mkrtchyan

Answer 1

如果你想要O(n)的时间复杂度和不使用额外的内存（因为已经指定了数组），可以使用Jon Bentley在他的书《编程珠玑 第2版》中介绍的算法。该算法交换所有元素两次。虽然不像使用链表那么快，但它使用的内存更少，并且概念上更简单。

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（含）的元素顺序反转。

- Jerry Penner

---

我想知道你什么时候会真正需要进行物理数组移位。 - Vinko Vrsalovic

@Vinko：也许这是计算应用于数组不同重叠部分的几个循环移位的更大任务的一部分。 - Rafał Dowgird

我会将assert(size>M)替换为M = M % size，并检查M==0。这样可以使函数更加灵活。 - Georg Schölly

就交换次数而言，该算法并不是最优的。 - Aryabhatta

@Vinko 我使用这个算法。我们有大约100个元素的小数组，并对它们执行大量操作。它必须是一个数组，因为我们需要对大多数操作进行随机访问。创建一个链表比就地交换要慢得多。所以对我们来说，这是一个性能问题。分配内存是昂贵的。 - martinus

Answer 2

最优解决方案

问题要求最快的方法。反转三次是最简单的方法，但它将每个元素移动两次，需要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的移位图示

第一个周期用黑色表示，数字表示操作顺序。第二个和第三个周期用灰色表示。

所需的周期数是 N 和 M 的最大公约数(GCD)。如果 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来减少移动次数的开销值得一试。 参考：http://www.geeksforgeeks.org/array-rotation/

- Isaac Turner

---

请查看Han的回答，了解如何隐式处理此问题。 - greybeard

这段代码比“Han的答案”简单易懂得多。但是C代码并不是如此。只需坚持答案顶部的“示例代码”。计算GCD是一个递归一行代码：size_t gcd(size_t a, size_t b) {return b == 0 ? a : gcd(b, a % b);}。 - Cris Luengo

这段代码在移位1时也快了10倍，在其他随机移位方面至少快了3倍，在我刚刚进行的一项快速测试中。它复制的内容更少。 - Cris Luengo

请参考我的答案，以获取更多关于此解决方案的直觉和理由。 - SomeStrangeUser

我认为最大公约数可以隐式计算为第一次循环中达到的最小非零索引。这可能就是 greybeard 所指的内容。 - Ciro Santilli OurBigBook.com

Answer 3

这只是一种表示方法。将当前索引保留为整数变量，遍历数组时使用模运算符来确定何时换行。移位仅更改当前索引的值，将其包装到数组的大小中。当然，这是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;
}

- Vinko Vrsalovic

---

这段话可以写得更清晰一些，例如“不是更新数组，而是更新一个整数来存储数组的当前起始位置”。但是这种方法会将 O(1) 的操作（推入/弹出）变为 O(n) 操作，所以显然存在权衡。 - Alice Purcell

这是一个非常好的“现实世界”解决方案，我希望每个人都能够使用。不过，我认为这个问题的含义是它是一个编程面试题，你需要就地修改数组。 - Sean Dunford

Answer 4

使用指针设置只需很少的时间，每个元素都指向下一个，而“最后一个”（实际上并没有最后一个，因为你说它是循环的）指向第一个。只需一个指向“开始”（第一个元素）的指针和可能的长度，就可以得到数组。现在，要进行位移操作，只需沿着圆圈移动起始指针即可。

寻求好算法，您会得到明智的想法。寻求最快的，您会得到奇怪的想法！

- gbarry

---

但是在遍历列表时，您不会每次都需要检查结束吗？ - Naveen

是的，但这很快。或者您可以使用模数（如果列表是2的幂，则使用按位AND）。 - Jason S

无论如何，您都会检查结束，即使使用传统数组也是如此。但是如果您保留长度，那么只需编写循环或将计数递减为零即可。 - gbarry

问题要求使用数组而不是链表。 - Javad

Answer 5

这个算法的时间复杂度为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;
}

- zhy2002

---

不错的算法。但是有太多的复制操作：list[] -> val，list[] -> tmp，val -> list[]，tmp -> val。如果你改变移动事物的顺序，你可以将一个循环的第一个元素复制到 val，然后直接将下一个元素向前复制（list[] -> list[]），重复此过程，直到最后一个元素，在那里写入 val。请参见此答案：https://dev59.com/cXNA5IYBdhLWcg3wpvtg#32698823 - Cris Luengo

Answer 6

一种非常简单的解决方案。这是一种非常快速的方式，我在这里使用一个与原始数组大小相同的临时数组，并在最后将其附加到原始变量上。 此方法使用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<a.length; i++)
        temp[(i+k)%a.length] = a[i];

    a = temp;

- DAme

---

临时数组占用O(n)空间而不是O(1)。 - Arsen Mkrtchyan

感谢您的建议。 - DAme

Answer 7

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的情况下也能正常工作。

- Ang

Answer 8

这是一个简单而高效的C++通用就地旋转函数，不到10行代码。

这段代码摘自我在另一篇问题的回答中。 如何旋转数组？

#include <iostream>
#include <vector>

// same logic with STL implementation, but simpler, since no return value needed.
template <typename Iterator>
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<int> 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';
}

- qeatzy

Answer 9

C数组右移函数。如果shift为负数，则该函数将数组向左移动。 它被优化以使用更少的内存。运行时间为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];
        }
    }
}

- Hexogen

Answer 10

根据您使用的数据结构，您可以在O(1)内完成操作。我认为最快的方法是将数组以链表的形式保存，并拥有一个哈希表，可以在“数组中的索引”和“条目指针”之间进行转换。这样，您可以在O(1)内找到相关的头和尾，并在O(1)内重新连接（并在切换后在O(1)内更新哈希表）。当然，这将是一个非常“混乱”的解决方案，但如果您只关心移位的速度，那么这样做就可以了（以牺牲更长的插入和查找数组时间为代价，但仍将保持O(1)）。

如果您的数据是纯数组，则无法避免O(n)。

从编码角度来看，这取决于您使用的编程语言。

例如，在Python中，您可以“切片”它（假设n是移位大小）：

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

我知道哈希查找在理论上不是O(1)，但我们现在是实际操作，而不是理论操作，至少我希望如此...

- Roee Adler