Python “原地”旋转数组
Python “原地”旋转数组
用户7685359
发布于 2020-08-21 19:50:27
发布于 2020-08-21 19:50:27
leetcode explore 初级算法第三题，旋转数组代码实现。原题链接：
https://leetcode-cn.com/explore/featured/card/top-interview-questions-easy/1/array/23/
题目分析
因为题目不是很长，这里把题目贴出来：
给定一个数组，将数组中的元素向右移动 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) 的 原地 算法。题目意思很简单，就是将数组往后移动 k 个位置，超出数组长度的从头开始计算。如果只是这个要求，题目特别简单，新开一个数组，然后将原数组移动 k 保留到对应位置即可。而题目的难点在于需要“原地”移动，空间复杂度为 O(1)，即不能新创建数组。
参考答案
首先分析题意，很容易想出移动位置公式：
target_pos = (pos + k) % nums_len剩下的就是解决“原地”的问题，很容易想到一种思路，就是移动后，从移动后的位置再接着去移动，同时保留原来位置的数据。这样只需要一个临时变量去保存被替换的变量即可。但中间有一些坑，比如：有些数据移动 k 个会形成一个循环，比如 [-1,-100,3,99] 和 k = 2，-1 到 3， 3 又回到 -1，-1 又到 3。如何解决这些循环问题是关键。
我的参考代码如下：
'''
@Author: demon
@Date: 2019-10-28 11:16:44
@LastEditors: demon
@LastEditTime: 2019-10-28 18:37:12
@Description: https://leetcode-cn.com/explore/featured/card/top-interview-questions-easy/1/array/23/ 旋转数组
'''
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: None Do not return anything, modify nums in-place instead.
"""
if not nums:
return
start_pos = 0
move_count = 0
nlen = len(nums)
for i in range(0, nlen):
if move_count == nlen:
break
pos = i
move_num = nums[pos]
while True:
target_pos = (pos + k) % nlen
tmp = nums[target_pos]
nums[target_pos] = move_num
move_count += 1
if target_pos == i or move_count == nlen:
break
pos = target_pos
move_num = tmp
if __name__ == "__main__":
s = Solution()
nums = [1, 2, 3, 4, 5, 6, 7]
s.rotate(nums, k=3)
print(nums) # [5, 6, 7, 1, 2, 3, 4]
nums = [-1, -100, 3, 99]
s.rotate(nums, k=2)
print(nums) # [3, 99, -1, -100]
nums = [-1, -100, 3, 99]
s.rotate(nums, k=4)
print(nums) # [-1, -100, 3, 99]
nums = [-1]
s.rotate(nums, k=4)
print(nums) # [-1]
nums = [-1]
s.rotate(nums, k=0)
print(nums) # [-1]
nums = [1, 2, 3, 4, 5, 6]
s.rotate(nums, k=3)
print(nums) # [4, 5, 6, 1, 2, 3]
nums = [1, 2, 3, 4, 5, 6]
s.rotate(nums, k=2)
print(nums) # [5, 6, 1, 2, 3, 4]上面给出了一些测试用例，基本上能覆盖一些比较坑的情况，如果你的代码能过这些用例，基本也就能 AC 了
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-10-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录