本文共 2576 字，大约阅读时间需要 8 分钟。
给定一个数组，将数组中的元素向右移动 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]
说明：
解题思路：运用python的切片，数组形式可以直接相加减。空间复杂度为O（1）的原地算法，效率很高。
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. """ nums_len = len(nums) nums[:] = nums[nums_len - k:] + nums[: nums_len - k] # #数组切片可以直接加减，放在一起 print (nums)
以下是Java版本：
题意是将序列首尾相连，然后向右滚动k步。
旋转数组，这种题的思路就是转三次，先整体转，再把两部分分别转即可,要注意的一点是k的取值，k可以很大，代表转了很多圈，所以计算的时候取mod，对于这种包含数字的题常要考虑是否取模
解法1：把数组逆序，然后逆序前k % length个，再逆序剩下的即可。
1. public class Solution { 2. public void rotate(int[] nums, int k) { 3. if(k <= 0) return ; 4. reverse(0, nums.length - 1, nums); 5. reverse(0, k % nums.length - 1, nums); 6. reverse(k % nums.length, nums.length - 1, nums); 7. } 8. public void reverse(int start, int end, int[] nums){ 9. while(start < end){ 10. int temp = nums[end]; 11. nums[end] = nums[start]; 12. nums[start] = temp; 13. start ++; 14. end --; 15. } 16. } 17. } 解法2：用anchor指向第0位，record=nums[anchor]，然后anchor指向rotate k位后的位置即anchor = (anchor + k)%length，记此位置的值为temp，交换temp和record，这样就把第0位的元素摆在了最终它应当在的位置，此时record记录的是当前anchor所指的数值，即第0位摆放在此处前的原有数值，用于下次的摆放。随着anchor的移动，record指向的数不断的被摆到最终位置，直至交换length次为止。此处存在一个问题就是anchor=(anchor + k)%length可能在计算若干次后又指回0，比如n = 10，k = 5，anchor重新等于0时显然数列不是最终状态，即尚未交换length次。这时就要使anchor后移一次从第1位开始，直至交换length为止。那么anchor的这种起始位置的移动最多有多少次呢？（外围循环结束条件）比如极端情况n = 7，k = 7，每次anchor都回到原位置，所以外围循环控制到k次。
注：用do...while，由于初始anchor = i，如果用while或for第一次循环条件就不满足，直接跳过循环不执行。
1. public class Solution { 2. public void rotate(int[] nums, int k) { 3. int len = nums.length; 4. int cnt = 0; 5. for(int i = 0; i < k ; i++){ 6. int anchor = i; 7. int record = nums[anchor]; 8. do{ 9. anchor = (anchor + k) % len; 10. int temp = nums[anchor]; 11. nums[anchor] = record; 12. record = temp; 13. cnt++; 14. }while(anchor != i); 15. if(cnt == len) break; 16. } 17. } 18. }
转载地址：http://npuvi.baihongyu.com/