55 lines
1.4 KiB
JavaScript
55 lines
1.4 KiB
JavaScript
/**
|
||
*https://leetcode.cn/problems/rotate-array/description/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {number[]} nums
|
||
* @param {number} k
|
||
* @return {void} Do not return anything, modify nums in-place instead.
|
||
*/
|
||
const rotate = function (nums, k) {
|
||
f1(nums, k);
|
||
// f2(nums, k);
|
||
};
|
||
|
||
/*
|
||
暴力法：直接copy整个数组，然后遍历复制后的数组从k位开始填充原数组
|
||
*/
|
||
function f1(nums, k) {
|
||
const copyNums = [...nums];
|
||
const size = nums.length; // 数组大小
|
||
for (let i = 0; i < size; i++) {
|
||
nums[(i + k) % size] = copyNums[i];
|
||
}
|
||
}
|
||
|
||
/*
|
||
反转法：观察发现，只要把数组选中，之后再选择前k个元素和剩下的n-k个元素即可实现题目要求的效果
|
||
*/
|
||
|
||
function f2(nums, k) {
|
||
const size = nums.length;
|
||
// 如果k等于0直接结束即可，反转是由性能损耗的
|
||
if (k === 0 || k === size) return;
|
||
k %= size; // 预防k>size
|
||
// 1. 反转整个数组
|
||
reverse(nums, 0, size - 1);
|
||
// 反转前面k个部分
|
||
reverse(nums, 0, k - 1);
|
||
// 反转剩下的n-k个部分
|
||
reverse(nums, k, size - 1);
|
||
}
|
||
|
||
// 反转数组的一个部分
|
||
function reverse(arr, start, end) {
|
||
while (start < end) {
|
||
// [arr[start], arr[end]] = [arr[end], arr[start]]; 交换效率低
|
||
const temp = arr[start];
|
||
arr[start] = arr[end];
|
||
arr[end] = temp;
|
||
start++;
|
||
end--;
|
||
}
|
||
}
|
||
|
||
const arr = [1, 2, 3, 4];
|
||
rotate(arr, 3);
|
||
console.log(arr);
|