LeetCode 189. 轮转数组

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

举个例子：

输入: 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]

思路解析

比较容易想到的一种方法就是借助一个跟原数组nums等长度的数组res，我们只需要将nums的第i个元素放到res的第 (i + k) % n 个位置就可以完成整个nums的轮转，这种方法的空间复杂度为O(n)，其中n为nums的长度。大家可以在纸上模拟一下整个过程，加深一下理解。

但是题目要求原地轮转，也就是空间复杂度为O(1)。

我们来看一下题目中给的例子，nums = [1,2,3,4,5,6,7]， k = 3，将nums轮转后的结果应该是[5,6,7,1,2,3,4]。

首先我们先对nums进行一次反转，反转后为[7,6,5,4,3,2,1]，观察下反转以后的元素的分布。

我们只需要对反转后的数组中前k个元素和后n - k个元素再分别反转一次就可以得到轮转后的结果。

c++代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        //先对k取余避免k大于nums的长度
        k = k % nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
    //反转nums中[left,right]区间的数字
    void reverse(vector<int>& nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            ++left;
            --right;
        }
    }
};

java代码

class Solution {
    public void rotate(int[] nums, int k) {
        // 对 k 取模，避免 k 大于 nums 的长度
        k = k % nums.length;
        // 整体反转数组
        reverse(nums, 0, nums.length - 1);
        // 反转前 k 个元素
        reverse(nums, 0, k - 1);
        // 反转剩余元素
        reverse(nums, k, nums.length - 1);
    }
    
    // 定义反转函数
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

python代码

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 对 k 取模，避免 k 大于 nums 的长度
        k = k % len(nums)
        
        # 定义反转函数
        def reverse(nums: List[int], left: int, right: int) -> None:
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        
        # 整体反转数组
        reverse(nums, 0, len(nums) - 1)
        # 反转前 k 个元素
        reverse(nums, 0, k - 1)
        # 反转剩余元素
        reverse(nums, k, len(nums) - 1)

复杂度分析

时间复杂度: O(n），其中n为nums的长度。

空间复杂度： O(1)。