189. Rotate Array 轮转数组

题目地址：https://leetcode.com/problems/rotate-array/description/

题目描述

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.
• Could you do it in-place with O(1) extra space?

题目大意

把一个数组向右移动k步，原地操作。

解题方法

切片

题目要求旋转，而且是从右边数k个值放到前面去进行旋转。需要注意的两点：

1、 k可能很大，也就是会旋转多次；
2、 原地翻转；

下面的做法是先去除了多次旋转的情况，然后通过遍历在原地翻转

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        while k > len(nums):
            k -= len(nums)
        changed = nums[-k:] + nums[:-k]
        for i in range(len(changed)):
            nums[i] = changed[i]

1 2 3 4 5 6 7 8 9 10 11 12

更优雅的方法，使用k对len进行求余，另外使用nums[:]即可原地翻转。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        nums[:] = nums[-k:] + nums[:-k]

1 2 3 4 5 6 7 8 9

递归

先把整个的翻转，再把前k个翻转，再把后面的翻转。

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        N = len(nums)
        k %= N
        self.reverse(nums, 0, N - 1);
        self.reverse(nums, 0, k - 1);
        self.reverse(nums, k, N - 1);

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发