在线性时间内旋转数组的算法

Question

如何i使用swap函数仅在线性时间内按时间旋转整数数组.

Answer 1

您可以使用reverse()帮助程序在线性时间内完成此操作.

// rotate array of size=size, by n positions
void rotate(int array[], int size, int n)
{
  // reverse array[0...size-1]
  reverse(array, 0, size-1);

  // reverse A[0...n-1]
  reverse(array, 0, n-1);

  // reverse A[n...size-1]
  reverse(array, n, size-1);
}

// reverse elements in the array[pos_from ... pos_to]
void reverse(int array[], int pos_from, int pos_to)
{
   ...
}

reverse(int array[], int pos_from, int pos_to)使用交换实现留给读者练习.提示:这可以在线性时间内完成.

Answer 2

假设我们有一个函数调用arr_reverse(arr,i,j),它arr在索引i和j使用swap函数之间反转数组的元素.

例:

arr = {1,2,3,4,5} 
i = 0
j = 2

那么函数将返回:

{3,2,1,4,5} 
 ^^^^^

实现这个功能是直截了当的O(N).

现在让我们使用这个函数来旋转数组.

arr     = {1,2,3,4,5} // input array
k       = 2 // amount of right rotation
result  = {4,5,1,2,3} // expected result 
l       = 5 // length of array.

Step 1: Call arr_reverse(arr,l-k,l-1) which is arr_reverse(arr,3,4)
we get {1,2,3,5,4} 
              ^^^

Step 2: Call arr_reverse(arr,0,l-k-1) which is arr_reverse(arr,0,2)
we get {3,2,1,5,4}
        ^^^^^     

Step 3: Call arr_reverse(arr,0,l-1) which is arr_reverse(arr,0,4)
we get {4,5,1,2,3} 
        ^^^^^^^^^

整个过程使用arr_reverse3次,制作它O(N)