轮转数组

LeetCode-189

// 时间复杂度为O(k*n)，因为每次循环需要移动整个数组，总共执行k次。
// 空间复杂度仍然为O(1)，因为只是交换了原始数组中的元素，没有使用额外的数组
var rotate = function(nums, k) {
  // 方案一、轮转k次
  let len = nums.length
  for(let i = 0; i < k; i++) {
      nums.unshift(nums.pop())
  }

  // 方案二、截取后面的再插入到前面去，省去多余的没必要的轮转
  k = nums.length % k
  nums.unshift(...nums.splice(-k))
  return nums

  // 方案三、暴力解法-时间复杂度：O(n * k)
  let len = nums.length, cur, temp
  for(let i = 0; i < k; i++) {
    temp = nums[len-1]
    for(let j = 0; j < len; j++) {
      // 向右移动位置
      cur = nums[j]
      nums[j] = temp
      temp = cur
    }
  }
  console.log(nums)
  return nums

  // 方案四、两两反转
  // 时间复杂度：O(n)，其中 n 是数组的长度，反转数组只需要遍历一次数组
  // 空间复杂度：O(1)。由于是原地旋转数组，所以没有使用额外的空间
  let len = nums.length
  k %= len
  // 反转整个数组
  reverse(nums, 0, len - 1)
  // 反转前k个
  reverse(nums, 0, k - 1)
  // 反转后k个
  reverse(nums, k, len - 1)
  console.log(nums)

  // 反转, 前后元素两两互换
  function reverse(nums, start, end) {
    let temp
    while (start < end) {
      temp = nums[start]
      nums[start] = nums[end]
      nums[end] = temp
      start++
      end--
    }
  }
}