leetcode 题目描述:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
- 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
- 要求使用空间复杂度为 O(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]
先说说笔者拿到题目的思路 刚开始的时候没有看到有空间复制度为1的要求 觉得 这不是很简单吗 新建一个新数组依次向后移动即可
不知道大家看得懂吗 就向后移几个位置然后取lens个值
上代码
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.
"""
lens = len(nums)
temp=nums+nums for i in range(lens): nums.insert(i,temp[((lens-k+i))]) #插入第i个位置
nums.pop(i+1) #将原来第i个位置的值删除
当然了 这种方法虽然可以通过leetcode测试 但是并不满足空间O(1)的要求
看了别人的代码 列举两个比较好的方法
第一个
def rotate3(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
for i in range(k): #进行k次操作
last = nums.pop() #删除最后一个值
nums.insert(0, last) #将最后一个值 放入第一个位置
print(nums)
可以看到 这种方法 每次将最后一个值删除 再存入第一个位置 很巧妙利用了pop()方法
第二个
def rotate4(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums[:] = nums[-(k % len(nums)):] + nums[:-(k % len(nums))]
print(nums)
第二个 简直无敌 python的简略 无人能敌 一行搞定
解释一下代码 如图应该很好的解释了 本质是根据k取2个区域 然后交换2个区域的顺序