如何在没有额外堆内存的情况下循环移位阵列？

Question

如何编写一个函数shift(int* arr, int k)循环移位一个整数k的数组？我不能说堆中的"malloc"内存.

例如,使用伪代码,shift([1, 2, 3, 4], 2)返回[3, 4, 1, 2]和shift([3, 1, 5, 5], 103)返回[1, 5, 5, 3].我已经尝试使用模数来实现这种效果,如这个Java程序所示,其中我基本上迭代了一半的数组和交换值.

public static int* shift(int* arr, int k) {
  int half_array_len = arr.length / 2;
  for (int i = 0; i < half_array_len; ++i) {
    // Swap!
    int newIndex = (i + k) % arr.length;
    int temp = arr[i];
    arr[i] = arr[newIndex];
    arr[newIndex] = arr[i];
  }
  return arr;
}

但是,我相信这个功能仅适用于偶数长度的数组.

如何实现shift任何长度的数组？答案可以是您想要的任何语言(Java,C++,Ook Ook!等).

Answer 1

(之前已被问过几次.)基本上,在Bentley的"Programming Pearls"(Juggling,Reversal和Block Swap算法)中描述和分析了三个专门用于解决这个问题的经典就地算法.这些幻灯片详细描述了它们

http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf

最简单的算法是反转算法.只需反转整个阵列,然后单独反转每个[n - k]和[k]块.完成.(从哪一端计算[k]块取决于移位的方向.)

当然,规范化第k一个是有意义的,即k = k % n确保k小于n.

PS在C++中,答案就是使用std::rotate,它完全符合您的要求.但我怀疑这是你寻求的答案.虽然你可能想看一些实现std::rotate(如果只发现它们通常使用Reversal算法:)