以o(n)复杂度向左或向右旋转一组位置

Question

我想编写一个程序,根据用户的输入(正 - >,负< - )将数组向右或向左移动一定数量的位置.该程序必须具有O(n)复杂性.我是用这种方式写的,但它不能正常工作.在示例中,输出应为"2,3,4,5,6,1",但在我的版本中为"6,2,3,4,5,1".

#include <stdio.h>
#include <string.h>
#include <math.h>

void rotate(int *array, int N, int D);

int main(){
    int i;
    int array[] = {1, 2, 3, 4, 5, 6};

    rotate(array, sizeof(array)/sizeof(int), 5);

    for(i=0; i<sizeof(array)/sizeof(int); i++)
        printf("%d\t", array[i]);

    return 0;
}

void rotate(int *array, int N, int D){
    int i, j, *tmp, d;

    tmp = malloc(abs(D) * sizeof(int));

    if(D<0){
        d = abs(D);
        for(i=d; i<N; i++){
            tmp[i%d] = array[i];
            array[i] = array[i-d];
            array[i-d] = tmp[i%d];
        }
    }
    if(D>0){
        for(i=(N-D-1); i>=0; i--){
            tmp[i%D] = array[i];
            array[i] = array[i+D];
            array[i+D] = tmp[i%D];
        }
    }
}

谢谢.

Answer 1

编程珍珠专栏2中的Jon Bentley描述了最优雅,最有效的解决方案.

旋转算法使用一个reverse()反转数组子序列的函数.从专栏引用:

让我们将问题视为将数组ab转换为数组 ba,但我们还假设我们有一个函数可以反转数组指定部分中的元素.从ab开始,我们反转a得到a_r b,反转b得到a_r b_r,然后反转整个东西得到(a_r b_r)_r,这正好是ba.

这就是你需要的.来自用户的输入定义了将数组分区为两个块A和B的位置.这是我的实现:

void reverse(int a[], int sz) {
  int i, j;
  for (i = 0, j = sz; i < j; i++, j--) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }
}

void rotate(int array[], int size, int amt) {
  if (amt < 0)
    amt = size + amt;
  reverse(array, size-amt-1);
  reverse(array+size-amt, amt-1);
  reverse(array, size-1);
}

我测试了它,它正在工作.另外,请注意如何处理负旋转:向左旋转size元素数组amt(即使用负值)size+amt与向右旋转元素相同.

享受优雅的代码,不要忘记在评论中包含学分(当然是Jon Bentley).