[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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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