3

如何编写函数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!等）。

4

2 回答 2

10

（之前被问过几次。）基本上，Bentley 的“编程珍珠”（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 算法 :)

于 2012-12-06T04:10:18.770 回答
1

我假设您的意思是您只能使用恒定数量的额外空间来执行此功能。可以O(n*(k mod n))使用以下算法（Python）及时完成一个温度：

def shift_one(array):
    temp = array[-1] #put last element of array in a temp
    for i in range(len(array)-1)[::-1]:
        array[i+1] = array[i] #put each element in the next slot
    array[0] = temp #then put the temp at the beginning
    return array

def shift(array, k):
    for i in range(k%len(array)):
        array = shift_one(array)
    return array

如果您实际上不受限于恒定的额外空间，则可以使用以下算法及时使用k额外空间来做到这O(n)一点（几乎相同）：

def shift(array, k):
    k = k % len(array) #shifting by len(array) does nothing
    temp = array[-k:] #copy out the last k elements
    for i in range(len(array)-k)[::-1]:
        array[i+k] = array[i]
    array[:k] = temp
    return array

此外，如果您有像 Python 中的列表可以做的比数组更多的列表，那么有一个非常简单的解决方案：

def shift(array, k):
    #take the last k elements and put them at the front
     return array[-k:]+array[:-k]
于 2012-12-06T04:04:01.757 回答