Leetcode189–旋转数组（多种方法解题，python）

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

编程语言：python

作者：黑暗主宰

邮箱：shengzhanhe@gmail.com

Leetcode189–旋转数组

题目描述

原题链接：

​ https://leetcode-cn.com/problems/rotate-array/ (中文)

​ https://leetcode.com/problems/rotate-array/ (英文)

题目描述：

​ 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例1：   输入: [1,2,3,4,5,6,7] 和 k = 3   输出: [5,6,7,1,2,3,4]   解释:   向右旋转 1 步: [7,1,2,3,4,5,6]   向右旋转 2 步: [6,7,1,2,3,4,5]   向右旋转 3 步: [5,6,7,1,2,3,4]

示例2：   输入: [-1,-100,3,99] 和 k = 2   输出: [3,99,-1,-100]   解释:   向右旋转 1 步: [99,-1,-100,3]   向右旋转 2 步: [3,99,-1,-100]

说明：

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为 O(1) 的 原地 算法。

解题思路

方法1：暴力求解

使用循环的方式，循环$k$，每次循环调整数组中元素的位置$O(n)$

def rotate1(nums, k):
    length = len(nums)
	for i in range(k):
    	tmp = nums[-1]
    	for j in range(length-1):
        	nums[-1-j] = nums[-2-j]
    nums[0] = tmp

官方提供的暴力求解使用的是java，转换为python

def rotate2(nums, k):
    length = len(nums)
    for i in range(k):
		last = nums[-1]
		for j in range(length):
            tmp = nums[j]
            nums[j] = last
            last = tmp

方法2：使用环状替换

官方的解释¹，第一次读可能有点绕，仔细读一下，对照着源码和下图，很容易就知道怎么回事了。

解释一个具体的例子：如下图 nums = [1,2,3,4,5,6], k = 2;

设 $nums$ 的长度为要知道 $k=n$ 时，就相当于循环于 $nums$ 没有旋转，所以要把 $k$ 限制到 $0\le k<n$ , 即 k = k % n，因为要原地修改数组，所以要建立一个 $tmp$ 变量来缓存数据。使用环状替换，每一次循环，数组中的元素都能直接到最终的位置。使用这种方法，我们要知道要从哪里开始移动，哪里停止。使用环形方法，每一次循环会移动 $\frac{n}{k}$ 个元素，要完成数组的翻转，每个元素都要调整位置，即需要调整 $n$ 次，所以我们要从原始下标为 $0$ 的地方开始，一直到 $k-1$，共循环 $k$ 轮，每次移动 $\frac{n}{k}$ 个元素，所以 $\frac{n}{k}\times k=n$。结合下文python源码更容易理解。

代码如下：

def totate(nums, k):
    length = len(nums)
    k = k % length

    count = 0
    start = 0

    while count < length:
        cur = start
        prev = nums[start]

        while True:
            next_index = (cur + k) % length
            tmp = nums[next_index]
            nums[next_index] = prev
            prev = tmp
            cur = next_index
            count += 1
            if cur == start:
                break
	 start += 1

方法3：使用python切片操作

def rotate1(nums, k):
    for i in range(k):
        '''
        tmp = nums[-1]
        nums[1:] = nums[:-1]
        nums[0] = tmp
        '''
       	nums[1:], nums[0] = nums[0:-1], nums[-1]

def rotate2(nums, k):
	length = len(nums)
	step = k % length
	nums[:] = nums[length-step:] + nums[:length]

方法4：使用python内置函数

使用pop删除数组的最后一个元素，然后使用insert函数把元素插入到首位置

def rotate(nums, k):
    for i in range(k):
		last = nums.pop()
		nums.insert(0, last)

方法5：增加空间复杂度（可以实现功能，但不符合题意）

时间复杂度$O(n)$，空间复杂度$O(n)$

def rotate(nums, k):
	length = len(nums)
    k = k % length
    # 使用新的列表来存储原来列表的元素，这里使用的是切片的方式 浅copy
    new_nums = nums[:]
    for i in range(k):
        nums[i] = new_nums[length-k+i]

	for j in range(k, length):
		nums[j] = new_nums[j-k]

欢迎大家关注我的个人公众号，同样的也是和该博客账号一样，专注分析技术问题，我们一起学习进步

注： 文中有写错的地方，欢迎大家不吝指正！！！

---

1. https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/ ↩︎