刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/rotate-array/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

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

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

进阶：

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

思路

额外数组

这个思路很简单，空间复杂度高一些记录下就好了

循环交替

这个思路就是不断往后交换，直接把数字摆到它应该在的位置，会有几个注意点：

• 用额外变量存下来下一个数字，便于持续往后计算
• 记录初始点，用是否回到初始点决定是否需要往右移动一位继续往后交换
• 记录总共摆放的次数，因为没有限制，会一直往后交换下去，其实我们简单画一下就明白，有可能交换回初始点时，很多位置就已经完成了，初始点右移是有可能把已经摆好位置的数字移动到错误位置，所以要限制总计交换次数

翻转数组

一图胜千言

大体思路就是这样了，上代码～

代码

交替

func rotate(nums []int, k int) {
	// 整除就直接return
	if k%len(nums) == 0 {
		return
	}
	p := 0
	// 把k取余，最多需要这么多起始点就够了
	k = k % len(nums)
    // 记录起始点
	startP := 0
    // 计算要摆放位置
	nextP := 0
    // 缓存下个要摆放的数字
	back := 0
    // 总计移动次数
	count := 0
    // 摆够了就不用继续了
	for startP < k && count < len(nums) {
		p = startP
		back = nums[p]
		for count < len(nums) {
            // 计算下个摆放位置
			nextP = (p + k) % len(nums)
            // 存下个摆放数字
			back, nums[nextP] = nums[nextP], back
            // 步进
			p = nextP
            // 统计摆放次数
			count++
            // 回到起始点就换个起始点
			if p == startP {
				break
			}
		}
        // 步进起始点
		startP++
	}
}

翻转

func reverse(a []int) {
	for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
		a[i], a[j] = a[j], a[i]
	}
}

func rotate(nums []int, k int) {
    // 计算旋转点
	n := k % len(nums)
    // 全量翻转
	reverse(nums)
    // 分别部分翻转
	reverse(nums[:n])
	reverse(nums[n:])
}