旋转数组(189)

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例

输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4]

输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100]

算法

pop()和unshift()

使用pop()和unshift()

当k等于nums.length时，数组循环一圈等于没有变，应先使用k % nums.length求出最少的转换次数

function rotate(nums, k) {
  const count = k % nums.length
  for(let i = 0; i < k; i++) {
    nums.unshift(nums.pop())
  }
  return nums
}

原地算法

原地、绝地反转算法

后面k % nums.length个元素和前面nums.length - k % nums.length个元素拼接成一个新数组，即为反转后的数组

其中反转点为nums.length - k % nums.length的位置

slice([start[, end]])，返回一个浅拷贝的数组，不会修改原数组

function rotate(nums, k) {
  const reversePoint = nums.length - k % nums.length
  if (reversePoint !== 0) {
    nums = nums.slice(reversePoint).concat(nums.slice(0, reversePoint))
  }
  return nums
}

另一种原地算法

由方法二可得：

splice(start[, deleteCount[, item1[, item2[, ...]]]])，会改变原数组，返回被删除的数组

function rotate(nums, k) {
	const count = k % nums.length
	return nums.splice(0, 0, ...nums.splice(nums.length - count))
}