刷题第三篇：力扣189.旋转数组

「这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战」

前言

空闲之余，继续刷一题，今天挑战一道中等难度的题目，也是一道数组相关的题目，小伙伴们看看这道题之后有什么想法呢。

题目分析

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

• 示例 1:

输入: nums = [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:

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

• 提示：

• 1 <= nums.length <= 2 * 104
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

• 进阶

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

代码分析

• 代码示例

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        int[] resultArr = new int[len];
        for (int i = 0; i < len; i++) {
            resultArr[(i + k) % len] = nums[i];
        }
        System.arraycopy(resultArr, 0, nums, 0, len);
    }
}
复制代码

• 创建一个新数组resultArr，长度与目标数组nums一致；
• 循环len次，将原数组nums中元素下标加上长度k，塞到新数组中。这里需要注意的是(i+k)%len中为什么要取模，这是因为题中未指明k和nums数组长度大小关系，k有可能超过数组长度，如果不取模，下标出现越界；
• 将新数组copy到原数组中。

通过几张图看上述流程：

• 原素组nums

• 假如k长度为9，对其取模，然后新增到新数组如下

我们看下这种方式的时间复杂度、空间复杂度：

• 时间复杂度： O(n)，n为数组长度。
• 空间复杂度： O(n)。

高阶解法

上面这种方式，其实大部分小伙伴还是能够想的出来的，但是对于题目中高阶解法的要求，我们还不满足。因此可以用数组翻转的方式来解答。

通过上述两张图我们可以看到：

• 如果k<len，忽略细节，最终得到的数组是将[k,len-1]挪到数组头部，[0,k-1]往后移动k个位置
• 如果k>len，会先将len取模，剩余步骤和k<len一致

所以，我们可以从这个角度去思考，首先进行整个数组的翻转，得到第一步结果：

我们观察翻转后结果，很明显这个顺序是不符合实际要求的，因此我们对翻转后的两个区间（[0,k-1]、[k,len-1]）再进行两次翻转，即可得到最终答案。

• 第二次翻转

• 第三次翻转

class Solution {
    public void rotate(int[] nums, int k) {
        k= k % nums.length;
        reverseArr(nums,0,nums.length-1);
        reverseArr(nums,0,k-1);
        reverseArr(nums,k,nums.length-1);
    }
​
    public void reverseArr(int[] nums, int left, int right) {
        while(left<right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}
复制代码

• 时间复杂度：O(n)，n为数组长度。
• 空间复杂度：O(1)。