Leetcode_190 Rotate Array

发表于 | 分类于

将包含 n 个元素的数组向右旋转 k 步。

例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

注意:

尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。

提示:

要求空间复杂度为 O(1)

“””

分析：主要考察反转数组

先把k跟数组长度取余数

把原数组划分为两个部分来看：前 n - k 个元素 [1,2,3,4]和 后k个元素 [5,6,7]

定义 reverse 反转数组方法，

前 n - k 个元素 [1,2,3,4] 反转后 [4,3,2,1]

对后k个元素 [5,6,7] 进行反转得到 [7,6,5]

将前后元素 [4,3,2,1,7,6,5] 反转：[5,6,7,1,2,3,4]

“””

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        if len(nums)<2 or k%len(nums)==0:
            pass
        k = k%len(nums)
        self.reverse(nums,0,len(nums)-k-1)
        self.reverse(nums,len(nums)-k,len(nums)-1)
        self.reverse(nums,0,len(nums)-1)
        
        
    def reverse(self,nums,start,end):
        while start<end:
            nums[start],nums[end]=nums[end],nums[start]
            start+=1
            end-=1