189. 轮转数组

题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 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 <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

题解

方案一

向后移动K个位置，因为是循环移动，所以最终效果跟 k % length 个位置是一样的，取 k = k % length。
将数组从 length - k 位置分割成两部分，前半部分和后半部分。
暂存后半部分 temparr
将前部分数据从最后一个数据向后移动k个位,从 length - k - i -1 --> length -i -1位置 ,向后移动 k 个位置。
将 temparr 数据从 0 --> k 位置，赋值给 nums 的前 k 个位置。

分析：

时间复杂度： $O (n)$
空间复杂度： $O (n)$

不是一个好的方案

class Solution:
    def rotate(self, nums, k):
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        k = k % length

        # print('origin', nums)

        temparr = nums[length -k:]

        # print('temparr', temparr)

        for i in range(length -k):
            nums[length -1 - i] = nums[length - k - i - 1]

        for i in range(k):
            nums[i] = temparr[i]

方案二：

数组反转

将 1-length 个数据反转
将前 1-k 个数据反转
将 k-length 个数据反转

分析：

时间复杂度： $O (n)$
空间复杂度： $O (1)$

class Solution:
    def rotate(self, nums, k):
        """
        Do not return anything, modify nums in-place instead.
        """

        def reverse(nums, start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1

        k = k % len(nums)

        reverse(nums, 0, len(nums) -1)
        reverse(nums, 0, k -1)
        reverse(nums, k, len(nums) -1)

189. 轮转数组 ​

题目描述 ​

题解 ​

方案一 ​

方案二： ​

189. 轮转数组

题目描述

题解

方案一

方案二：