（初级）9.- 旋转数组 (Rotate Array)

题目描述

https://leetcodechina.com/

将包含 n 个元素的数组向右旋转 k 步。

例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。

注意：
尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。

提示:
要求空间复杂度为 O(1)

解法1

借助O(n)的空间解法。再利用(i + k) % n = 旋转后的位置，可以将原有数组中的数据复制到新数组中。

例如：

3元素在数组中的2位置上，(2+3) % 7 = 5
5元素在数组中的4位置上，(4+3) % 7 = 0
6元素在数组中的5位置上，(5+3) % 7 = 1
7元素在数组中的6位置上，(6+3) % 7 = 2

根据以上可以推断出，诸如将一个数组向右偏移或者旋转多少步等之类的题目，可以通过(元素位置+偏移或旋转步数) 模与 数组长度可以得到偏移或者旋转之后的元素位置。

package roatearray

func rotate(nums []int, k int) {
    result := make([]int, len(nums))
    for i := 0; i <= len(nums)-1; i++ {
        result[(i+k)%len(nums)] = nums[i]
    }
}

解法2
依旧可以利用(i+k)%n等于新i的思路，不过这次是每次调换一个元素，后一个元素的调换基于上一个的位置。

例如：让数组[1,2,3,4,5,6,7]向右旋转1，可以按照以下步骤来：

// 1
// 1, 2, 3, 4, 5, 6, 7

//   3
// 1, 2, 1, 4, 5, 6, 7

//       5
// 1, 2, 1, 4, 3, 6, 7

//          7
// 1, 2, 1, 4, 3, 6, 5

//   2
// 1, 7, 1, 4, 3, 6, 5

//       4
// 1, 7, 1, 2, 3, 6, 5

//      6
// 1, 7, 1, 2, 3, 4, 5

// 1
// 6, 7, 1, 2, 3, 4, 5

func rotate2(nums []int, k int) {
    k = k % len(nums)
    if (len(nums) == 0) || (k == 0) {
        return
    }
    start, i := 0, 0
    pre := nums[i]
    count := 0
    for {
        if count >= len(nums) {
            break
        }
        i = (i + k) % len(nums)
        temp := nums[i]
        nums[i] = pre
        if i == start {
            start++
            i++
            pre = nums[i]
        } else {
            pre = temp
        }
        count++
    }
}