在 o(n) 复杂度中按一定数量的位置向左或向右旋转数组 [英] Rotate array left or right by a set number of positions in o(n) complexity

问题描述

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

I want to write a program that shifts an array by a set number of positions right or left based on the user's input (positive ->, negative <-). The program has to have O(n) complexity. I've written it this way but it doesn't work as it should. In the example the output should be "2, 3, 4, 5, 6, 1" but in my version is "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];
        }
    }
}

谢谢.

推荐答案

Jon Bentley 在 Programming Pearls Column 2 中描述了众所周知的最优雅、最高效的解决方案.

Jon Bentley in Programming Pearls Column 2 describes what has came to be known as the most elegant, efficient solution.

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

The rotation algorithm uses a function reverse() that reverses subsequences of the array. Quoting from the column:

我们把问题看成是将数组ab转换成数组ba，但我们也假设我们有一个函数可以反转数组指定部分的元素.从 ab 开始，我们反转a得到a_r b，反转b得到a_r b_r，然后反转整个事情得到 (a_r b_r)_r，这正是 ba.

Let's view the problem as transforming the array ab into the array ba, but let's also assume that we have a function that reverses the elements in a specified portion of the array. Starting with ab, we reverse a to get a_r b, reverse b to get a_r b_r, and then reverse the whole thing to get (a_r b_r)_r, which is exactly ba.

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

This is what you need. The input from the user defines the place where you will partition the array into two blocks A and B. Here's my implementation:

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 到右边.

I tested it and it's working. Also, note how negative rotations are handled: rotating an array of size elements amt to the left (i.e. with negative values) is the same as rotating it size+amt to the right.

享受优雅的代码，不要忘记在评论中加入署名(当然是 Jon Bentley).

Enjoy the elegant code, and don't forget to include credits in a comment (to Jon Bentley, of course).

这篇关于在 o(n) 复杂度中按一定数量的位置向左或向右旋转数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！