[LeetCode]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?

题目大意:

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

例如,数组[1,2,3,4,5,6,7]包含元素个数n = 7,向右旋转k = 3步,得到[5,6,7,1,2,3,4]。

至少有3种不同的解题方法,最好使用O(1)的额外空间,“就地”完成数组旋转。

解题思路及代码:

参考LeetCode Discuss(https://oj.leetcode.com/discuss/26088/two-solution-with-extra-memory-dont-know-the-third-one-yet-idea)

解法一 [ 时间复杂度O(n),空间复杂度O(1) ]:

以n - k为界,分别对数组的左右两边执行一次逆置;然后对整个数组执行逆置。

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

Python代码:

class Solution:
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
        n = len(nums)
        k %= n
        self.reverse(nums, 0, n - k)
        self.reverse(nums, n - k, n)
        self.reverse(nums, 0, n)

    def reverse(self, nums, start, end):
        for x in range(start, (start + end) / 2):
            nums[x] ^= nums[start + end - x - 1]
            nums[start + end - x - 1] ^= nums[x]
            nums[x] ^= nums[start + end - x - 1]

注释:

Python中两个数交换可以用如下方法实现:

a, b = b, a

或者:

a ^= b
b ^= a
a ^= b

解法二 [ 时间复杂度O(n),空间复杂度O(1) ]:

将数组元素依次循环向右平移k个单位

Python代码:

class Solution:
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
        n = len(nums)
        idx = 0
        distance = 0
        cur = nums[0]
        for x in range(n):
            idx = (idx + k) % n
            nums[idx], cur = cur, nums[idx]
            
            distance = (distance + k) % n
            if distance == 0:
                idx = (idx + 1) % n
                cur = nums[idx]

解法三 [ 时间复杂度O(n),空间复杂度O(n) ]:

注:此方法需要构造新的数组,不满足提示描述中的“就地”旋转条件

class Solution:
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
        n = len(nums)
        if k > 0 and n > 1:
            nums[:] = nums[n - k:] + nums[:n - k]

 

本文链接:http://bookshadow.com/weblog/2015/02/24/leetcode-rotate-array/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

评论
  1. 爱美的玛丽娜 爱美的玛丽娜 发布于 2015年11月26日 11:43 #

    第二个没看懂...T,T

  2. 在线疯狂 在线疯狂 发布于 2015年11月26日 23:44 #

    nums = [1,2,3,4,5,6,7], k = 3的运行过程中nums和cur的变化过程:
    0 -> 3 [1, 2, 3, 1, 5, 6, 7] 4
    3 -> 6 [1, 2, 3, 1, 5, 6, 4] 7
    6 -> 2 [1, 2, 7, 1, 5, 6, 4] 3
    2 -> 5 [1, 2, 7, 1, 5, 3, 4] 6
    5 -> 1 [1, 6, 7, 1, 5, 3, 4] 2
    1 -> 4 [1, 6, 7, 1, 2, 3, 4] 5
    4 -> 0 [5, 6, 7, 1, 2, 3, 4] 1

  3. Kevin Kevin 发布于 2016年5月13日 15:12 #

    class Solution:
    # @param nums, a list of integer
    # @param k, num of steps
    # @return nothing, please modify the nums list in-place.
    def rotate(self, nums, k):
    n = len(nums)
    k = k % n
    nums[:] = nums[n-k:] + nums[:n-k]

    切片更简洁

  4. Nigel Nigel 发布于 2016年9月7日 18:35 #

    第一种解法,如果K大于字符串的长度,则结果有问题。

  5. 在线疯狂 在线疯狂 发布于 2016年9月7日 19:57 #

    k %= n,这行代码将k限制在字符串长度范围之内

张贴您的评论