题目描述

通过K步将一个有着n个元素的数组旋转到右侧。例如，给定n = 7和k = 3，数组[1,2,3,4,5,6,7]会被旋转成[5,6,7,1,2,3,4]。尽你可能尝试多种解决方案，这里至少存在3种不同的方式去解决这个问题。要求使用O(1)的额外空间实现。

我的解法——三次反转数组

三次反转数组：第一次反转所有、第二次反转前一半、第三次反转后一半
n的复杂度。
小坑：可能k>length，会越界，所以用k = k % length约束
结果：beat 16.40%

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.
        """
        
        length = len(nums)
        k = k % length
        for i in range(length / 2):
            nums[i],nums[length - i - 1] = nums[length - i - 1],nums[i]
        for i in range(0,k / 2):
            nums[i],nums[k - i - 1] = nums[k - i - 1],nums[i]
        for i in range(0,(length - k) / 2):
            nums[i + k],nums[length - i - 1] = nums[length - i - 1],nums[i + k]

其他解法——循环替换

直接将数组每个数字放在移动后的位置。
一个小case如下：

n的时间，1的空间。

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int count = 0;
        for (int start = 0; count < nums.length; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.length;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
}

参考答案

https://leetcode.com/problems/rotate-array/solution/