跳转至

LeetCode: 189.旋转数组

1、题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

  • 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
  • 要求使用空间复杂度为 O(1) 的原地算法。

2、解题思路

2.1 缓冲数组法

​ 设置一个与当前数组同样大小的数组，将原数组中的所有的元素使用取余，计算出位置，直接赋值

2.2 单步移动法

​ 每一次右旋移动一次，根据需要移动的数量，多次移动

2.3 分组法

​ 分组法较为巧妙

例如，1，2，3，4，5，6，7

​ 我们想要右移3位，那么实际上可以如何实现呢？

​ 我们将1，2，3，4只有移动到右面底部，然后将5，6，7平移到左面，就得到结果了

​ 但是，如果想要不借助其他的空间移动，我们发现，直接取反就可以做到，不过1，2，3，4的位置是反着的，5，6，7的位置也是反着的

​ 因此，根据移动的步数，进行分组，然后将组内部元素取反，再整体取反，就得到想要的结果了

void reverse(int *nums, int left, int right) {
    int length = right - left + 1;
    if (length <= 1) {
        return;
    }

    for (int i = 0; i < length / 2; i++) {
        nums[left + i] ^= nums[right - i];
        nums[right - i] ^= nums[left + i];
        nums[left + i] ^= nums[right - i];
    }
}

void rotate(int *nums, int numsSize, int k) {
    int step = k % numsSize;
    if (step == 0) {
        return;
    }

    reverse(nums, 0, numsSize - step - 1);
    reverse(nums, numsSize - step, numsSize - 1);
    reverse(nums, 0, numsSize - 1);
}