数组循环右移

约定不等于承诺〃 2024-04-18 08:01 75阅读 0赞

数组循环右移问题：给定一个长度为n的数组，将其向右循环移动k位得到一个新的数组。要求空间复杂度为O(1)。（此题为LeetCode上的编程题，但是在我遇到多益网络的面试之前我是不知道此题是LeetCode上的，所以当时我并不清楚此题的算法）

例：长度为n=5的数组a的元素为\{1,2,3,4,5\}，将其右移k=3位后得到\{3,4,5,1,2\}。其移动过程为\{1,2,3,4,5\}向右移动一位得到\{5,1,2,3,4\}，向右移动两位得到\{4,5,1,2,3\}，则向右移动三位得到\{3,4,5,1,2\}。由于当时面试之前我并没有见过此题，所以一时半会想不到算法，但之后发现此题并不难，完全可以看做普通的数组逆序来处理。循环右移k位，则数组中前n-k个元素会被移动，同时数组中最后k位的元素将会被移动到数组开始的位置。那么我们可以将原始数组分为两部分进行单独处理，先将数组中前n-k个元素进行逆序，之后再将最后的k个元素进行逆序，最后将整个数组再进行一次逆序即可。这样的话，其对应的代码为：

#include <stdio.h>
    void Right_Move(int a[], int n, int k)
    {
        while (n < k)
        {
    	int temp = a[n];
    	a[n] = a[k];
    	a[k] = temp;
    	n++;
    	k--;
        }
    }
    int main()
    {
        int a[] = { 1, 2, 3, 4, 5 };
        int len = sizeof(a) / sizeof(a[0]);
        printf("原始数组为:\n");
        for (int i = 0; i < len; i++)
        {
    	printf("%d ", a[i]);
        }
        printf("\n");
        int k = 3;
        Right_Move(a, 0, len - k - 1);
        Right_Move(a, len - k, len - 1);
        Right_Move(a, 0, len -  1);
        printf("循环右移%d位后:\n", k);
        for (int i = 0; i < len; i++)
        {
    	printf("%d ", a[i]);
        }
        printf("\n");
        return 0;
    }

![20190903190631523.png][]

[20190903190631523.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/dbff9940bf4e4079a0e036c5cf31515e.png