题目链接:https://leetcode-cn.com/problems/rotate-array/

题目描述:

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

解法1

最暴力的解法,首先找出一个最原子的操作,k=1的操作就是一个元素交换的操作,在此基础上循环k次。

1
2
3
4
5
6
7
8
9
10
11
12
var rotate = function(nums, k) {
let len = nums.length;
for(let i = 0; i < k; i++) {

let temp = nums[len-1];
for(let j = len - 1; j > 0; j--) {
nums[j] = nums[j-1]
}
nums[0] = temp;

}
};

上述解法,因为是两层循环,最外层是移动的k次,最里层是一个遍历交换元素,因此时间复杂度O(n*k), 没有接住额外的空间,空间复杂度O(1)。

解法2

直接使用数组截取的方法,然后拼接起来依次赋值给原数组,缺点就是需要额外开辟一些空间存储临时值。

1
2
3
4
5
6
7
8

var rotate = function(nums, k) {
let temp = nums.slice(nums.length - k);
let copy = nums.slice(0, nums.length - k);

let res = temp.concat(copy);
res.forEach((item, index) => nums[index] = item);
};

解法3

非常巧妙的一个解法,可以先整体反转,然后前k个反转一遍,后面的再反转一下,一共反转三次就完成了目的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function reverse (nums, start, end) {
while(start < end) {
let temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}

var rotate = function(nums, k) {
k = k % nums.length;

reverse(nums, 0, nums.length-1); // 整体反转一遍
reverse(nums, 0, k-1); // 前k个反转一遍
reverse(nums, k, nums.length-1); // 后面的序列反转一遍
};