【LeetCode 189】旋转数组

189. Rotate Array

题目难度: 简单

Rotate an array of _n_ elements to the right by _k_ steps.

For example, with _n_ = 7 and _k_ = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint:
Could you do it in-place with O(1) extra space?

Related problem:

解题思路

先一半一半的旋转,然后在整个旋转。最后实现向右移动的效果

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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.
      """
       k = k % len(nums)
       self.reverse(nums, len(nums) - k, len(nums))
       self.reverse(nums, 0, len(nums) - k)
       self.reverse(nums, 0, len(nums))

   def reverse(self, nums, l, r):
       i = l
       j = r - 1
       while j > i:
           temp = nums[i]
           nums[i] = nums[j]
           nums[j] = temp
           i = i + 1
           j = j - 1
黄小豆 wechat
关注我的公众号,同步推送博客内容
坚持原创技术分享,您的支持将鼓励我继续创作!
0%