跳转至

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);
}