【LeetCode Hot100】189.轮转数组-三种解法以及效果评估

题目描述

给定一个整数数组 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 <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

不管轮转几步会发现，数组总是像是被分成了左右两份，有一个断点的感觉

方法一（针对原数组去找那个断点）

从原数组找到断点之后，从断点开始往后push进新数组
然后再从原数组第一位开始push进新数组

varrotate=function(nums,k){constlen=nums.length;k=k%len;constnewArr=[];for(leti=len-k;i<len;i++){newArr.push(nums[i])}for(leti=0;i<len-k;i++){newArr.push(nums[i])}for(leti=0;i<len;i++){nums[i]=newArr[i]}};

效果评估：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方法二（针对新数组去找那个断点）

原数组都是从第一位开始遍历，然后从新数组的断点位置开始push数据

varrotate=function(nums,k){constlen=nums.length;k=k%len;constnewArr=newArray(len);for(leti=0;i<len;i++){letidx=(i+k)%len;newArr[idx]=nums[i];}for(leti=0;i<len;i++){nums[i]=newArr[i];}};

效果评估：

• 时间复杂度：O(n)
• 空间复杂度：O(n)
  

方法三

https://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/?envType=study-plan-v2&envId=top-100-liked
力扣官方题解方法二：环状替换