LeetCode|LeetCode 探索初级算法-数组（03 旋转数组-20200316） leetcode|算法|python|探索初级算法

03 旋转数组-20200316 题目
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例

输入: [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]

说明

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

注意事项

循环移动，最笨的办法就是逐一移动，因为要求空间复杂度为O(1)，所以不能另外开辟新数组。
题目不要求返回值，直接对数组操作。
不用考虑数组长度和k的大小关系，就是移动就行。
写出来三种算法。

思路一
先来个笨办法，在数组后面加一项，逐个向后移，再把最后一项移到最前面，这个方法的时间复杂度应该很高。
修改经历：
1. 我知道时间会很长，但是没想到超出了时间限制？！！头大，两层循环看来不行啊。（第一次提交）
心得体会：
这个方法，我没有在题解关于Python 3上看到，可能就是太笨了吧。
最终代码展示：

class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ for i in range(k%len(nums)): temp = nums[-1] for j in range(len(nums)-1, 0, -1): nums[j] = nums[j-1] nums[0] = temp

思路二
我想我可能是个傻子。。。直接把数组后面的截取放到前面不好吗？但是这样就可能要新开辟一个数组了。
修改经历：
1. 没有考虑到输入数组为[1]，k=0的情况（第一次提交）
2.没有考虑到k大于数组长度的情况，比如[1]，k=2。（第二次提交）

执行用时 :36 ms, 在所有 Python3 提交中击败了95.39%的用户
内存消耗 :13.8 MB, 在所有 Python3 提交中击败了97.58%的用户

心得体会：
我是真的没有想到，思路二竟然能通过，而且排名还这么靠前。。。O(1)的空间复杂度呢？这不就是相当于O(N)的空间复杂度了吗？

看到一种非常简单的写法：

lenth = len(nums) nums[:] = nums[lenth-k:]+nums[:lenth-k]

这个真的是牛逼了，连临时变量都不需要了

最终代码展示：

class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ if k == 0 or len(nums) == 1: pass else: nums1 = nums[-k%(len(nums)):] nums2 = nums[:-k%(len(nums))] nums[:k%(len(nums))] = nums1 nums[k%(len(nums)):] = nums2

思路三
这个思路是在题解上看到的，把最后一个pop()，再插入第一项。。。代码就两行。看来Python还是没玩转啊。
最终代码展示：

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. """ k=k%len(nums) for i in range(k): nums.insert(0,nums.pop())

思路四
这是看题解的大神写得，我觉得这种是最复合题目要求的空间复杂度为O(1)的要求了。这就是翻转法，我把解法贴出来了。

三次反转
对于[1,2,3,4,5,6,7]，
根据k=k\%n，将数组分为两段：

第一段，对应数组下标范围[0,n-k-1]段，即[1,2,3,4]

第二段，对应数组下标范围[n-k,n-1]，即[5,6,7]

分为三步：

反转第一段，[4,3,2,1,5,6,7]

反转第二段，[4,3,2,1,7,6,5]

反转整体，[5,6,7,1,2,3,4]

完成！

心得体会：
这个方法妙哉啊，要好好记下来！这个是怎么想到的呢？
【LeetCode|LeetCode 探索初级算法-数组（03 旋转数组-20200316）】最终代码展示：

class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ def swap(former, latter): while former < latter: nums[former], nums[latter] = nums[latter], nums[former] former += 1 latter -= 1 k = k % (len(nums)) swap(0, len(nums)-k-1) swap(len(nums)-k, len(nums)-1) swap(0, len(nums)-1)