设计一个算法,把一个含有 N 个元素的数组循环右移 K 位,要求时间复杂度为 O (N),且只允许使用两个附加变量。

2 1 收藏


直接登录
最新评论
  • Majesty   2015/10/09

    说一下大概思路:
    首先让K=K%arr.length,如果K=0直接返回;

    其次,分两种情况:
    1,如果K不能整除arr.length,则一组长度为arr.lengh的置换就搞定;
    2,else,则分为K组长度为arr.length/K的置换来搞定;

    ————–
    思路来自于组合数学里关于置换的一些知识。

  • KeyType a[] , tmp0 , tmp1;
    int count = 0 , i=k;
    tmp0 = a[0]; //tmp0保存当前需要交换的元素
    while(count<n){
    tmp1 = a[i]; //tmp1保存下次需要交换的元素
    a[i] = tmp0;
    tmp0 = tmp1;
    i = (i+k)%n; //寻找下个元素应该交换去的位置
    count++;
    }

  • 小牙 在读硕士 2015/10/15

    数组翻转问题

  • 王先生 学生 2015/10/16

    先看这样一个简单的例子
    假设原数组序列为abcd1234,要求变换成的数组序列为1234abcd,即循环右移了4位。比较之后,不难看出,其中有两段的顺序是不变的:1234和abcd,可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成:
    1. 逆序排列abcd:abcd1234 → dcba1234;
    2. 逆序排列1234:dcba1234 → dcba4321;
    3. 全部逆序:dcba4321 → 1234abcd。
    得到源代码如下:
    void Reverse(int* a,int begin,int end){
    for(;begin<end;begin++,end–){
    int temp=a[end];
    a[end]=a[begin];
    a[begin]=temp;
    }
    }
    int* RightShift(int* a,int N,int k){//N表示数组的长度,k表示右移的位数
    k%=N;
    Reverse(a,0,N-k-1);
    Reverse(a,N-k,N-1);
    Reverse(a,0,N-1);
    return a;
    }

  • 開物館主   2015/10/22

    一开始写错了~~
    Python下的一种方法
    假设该数组的类型是list
    def move_right(lt, K):
    temp_1 = lt + lt
    temp_2 = []
    for i in range(N):
    temp_2.append(temp_1[N-K+i])
    return temp_2

  • 靳遗山   2015/10/22

    new一个长度为N的新数组,然后将值依次赋予新数组

  • honeywell2012   2015/10/23

    这是2010 年还是11年计算机考研全国卷408的试题…

  • 江之涛涛   2015/10/23

    看了答案,觉得大家答得太普通,这玩意不就是循环链表吗?新搞个数组arr1,2倍长度。再定义一个指针数组arr2。从arr1中间位置起,根据左移动或右移动,新数组arr2的首指针指向那个就行,然后free超出的空间,时间复杂度肯定小于O(N)。仅限C或C++哦

  • 吖沛   2015/10/27

    如果可以的话,我会想直接改变数组起始地址,前移k位,然后申请空间,再将最后的k位补回前面。当然,前提是能够操作,且有空间操作