52 - 旋转数组

题目

给定一个数组，将数组中的元素向右移动 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]

说明:

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

• 要求使用空间复杂度为 O(1) 的 原地 算法。

解答

作者：LeetCode 链接：https://leetcode-cn.com/problems/two-sum/solution/xuan-zhuan-shu-zu-by-leetcode/

环形替换

第一反应是替换，数组多加一位（其实可以用temp存），被替换的数放进temp，从而交换两个数的位置。

但看到题解，发现如果数组长度是移动数k的整数倍，那么没有全部遍历完数组，就会回到出发时的数字了。

题解给出的方法，不是一口气放完所有的数字，而是一轮轮的放。

第一轮把i%k==0的数字替换了，第二轮把i%k==1的数字替换了，以此类推，直到回到了i%k==0，即i==k的时候，所有数字也就都替换了。

https://leetcode.com/problems/rotate-array/discuss/198324/Go-solution-using-cyclic-replacement

func rotate(nums []int, k int) {
    length := len(nums)
    k = k % length
    var count int
    for i := 0; count < length; i++ {
        j := i
        cur := nums[i]
        for {
            j = (j + k) % length
            nums[j], cur = cur, nums[j]
            count++
            if j == i {
                break
            }
        }
    }
}

Runtime: 52 ms, faster than 89.40% of Go online submissions forRotate Array.

Memory Usage: 7.6 MB, less than 66.67% of Go online submissions forRotate Array.

• count统计总替换的次数，不能让它操作总的数组次数

• j是小循环里面的替换

• 小循环是想把该取余下面的所有数都替换掉

java里面的do..while可以用go的for..if..break来代替。

var rotate = function (nums, k) {
  const len = nums.length
  k %= len
  let count = 0
  for (let i = 0; count < len; i++) {
    let j = i
    cur = nums[i]
    while (1) {
      j = (j + k) % len
      let temp = cur
      cur = nums[j]
      nums[j] = temp
      count++
      if (j === i) {
        break
      }
    }
  }
};

Runtime: 60 ms, faster than 93.71% of JavaScript online submissions for Rotate Array.

Memory Usage: 35.3 MB, less than 73.68% of JavaScript online submissions for Rotate Array.

可以说是非常快的一次js程序了

三次翻转

旋转数组 k 次，k%n个尾部元素会被移动到头部，剩下的元素会被向后移动。

因此这也就相当于，先将所有元素反转。然后反转前 k 个元素，再反转后面 n-k个元素。

func reverse(nums []int, start, end int) {
    for start < end {
        nums[start], nums[end] = nums[end], nums[start]
        start++
        end--
    }
}

func rotate(nums []int, k int) {
    k %= len(nums)
    reverse(nums, 0, len(nums)-1)
    reverse(nums, 0, k-1)
    reverse(nums, k, len(nums)-1)
}

Runtime: 52 ms, faster than 89.40% of Go online submissions forRotate Array.

Memory Usage: 7.6 MB, less than 66.67% of Go online submissions forRotate Array.

const reverse = function (nums, start, end) {
  while (start < end) {
    let temp = nums[start]
    nums[start] = nums[end]
    nums[end] = temp
    start++
    end--
  }
}
var rotate = function (nums, k) {
  const len = nums.length
  k %= len
  reverse(nums, 0, len - 1)
  reverse(nums, 0, k - 1)
  reverse(nums, k, len - 1)
};

Runtime: 64 ms, faster than 85.24% of JavaScript online submissions for Rotate Array.

Memory Usage: 35.4 MB, less than 47.37% of JavaScript online submissions for Rotate Array.

js好像不能用这种互换的写法，只能加一个中间变量

nums[start], nums[end] = nums[end], nums[start]

优化

三次翻转似乎能用go的语言特性来优化一下

作者：elliotxx

链接：https://leetcode-cn.com/problems/two-sum/solution/108mssan-ci-fan-zhuan-de-go-shi-xian-by-elliotxx/

func rotate(nums []int, k int) {
    k %= len(nums)
    ans := append(nums[len(nums)-k:], nums[:len(nums)-k]...)
    nums = append(nums[:0], ans...)
}

Runtime: 48 ms, faster than 98.84% of Go online submissions forRotate Array.

Memory Usage: 7.5 MB, less than 100.00% of Go online submissions for Rotate Array.

我感觉还能再优化一下，直接不用另外设中间变量：

func rotate(nums []int, k int) {
    k %= len(nums)
  nums = append(nums[:0], append(nums[len(nums)-k:], nums[:len(nums)-k]...)...)
}

Runtime: 52 ms, faster than 89.40% of Go online submissions forRotate Array.

Memory Usage: 7.5 MB, less than 100.00% of Go online submissions for Rotate Array.

不过反而好像速度变慢了。。

测试

go判断两个slice是否相等的函数：

参考

func isEqual(a, b []int) bool {
    if len(a) != len(b) {
        return true
    }
    if (a == nil) != (b == nil) {
        return true
    }
    for i, elem := range a {
        if elem != b[i] {
            return true
        }
        runtime.Gosched()
    }
    return false
}

第8行，文章说要加一个越界检查，但我感觉不用，因为如果长度不相等，第3行就直接return了，能进来的都是长度相等的slice。参考