这是leetcode的一道算法题目,主要是讲解数组的旋转。【189-Rotate Array】
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
题目的主要是意思是:向右旋转一个有n元素的数组k个步骤;比如一个数组的长度n=7, 移动的步数k=3,数组[1, 2, 3, 4, 5, 6, 7],旋转之后的数组为[5,6,7,1,2,3,4]。
从题目中我们能够知道,其实我们没有必要移动k个步骤,移动k%n个步骤就行了,因为中间的一些步骤都是重复循环。我们只需要移动最后一个循环中剩余的几步即可完成,这样就能减少很多的步骤和操作。
leetcode能够选择多个编程进行回答,而我选择的是JavaScript,不过使用JavaScript进行编程时,里面有个提示非常的重要:
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
如果用JavaScript的话,那么你的程序必须是:不用返回任何数据,而且,只能修改nums,不能替换nums的数据,比如:nums=***
。
刚开始没有注意到这句话,就想着,把最后k个数获取到,然后跟剩余的拼接起来,并赋值给nums即可。于是就产生了下面的程序:
var rotate = function(nums, k) {
var len, after;
len = nums.length;
k = k%len; // 对k进行处理
after = nums.splice(-k, k); // 截取最后k个元素
nums = after.concat(nums); // 最后k个元素与前面剩余的元素拼接起来
};
用这个程序竟然没有通过,后来才注意到这个提示。我们只能对nums数组进行操作,即我们必须使用一些能够改变数组本身的方法,比如push(), pop, shift(), unshift(), splice()等;而slice(), concat()等这些方法是不能使用的,因为它们只是返回了我们需要的数据,但是原数组并没有发生改变。
现在让我们回忆一下这些方法的使用:
- push(elem0, elem1, elem2, ...) 向数组的末尾添加元素,并返回新的长度
- pop() 删除数组中最后的一个元素,同时返回该元素
- shift() 把数组的第一个元素从其中删除,并返回第一个元素的值
- unshift(elem0, elem1, elem2, ...) 向数组的开头添加一个或更多元素,并返回新的长度
- splice(start, len, elem0, elem1, elem2, ...) 从数组的start位置删除len个元素,同时在该位置填充elem0, elem1等元素。如果elem为空,则直接进行删除,同时返回被删除的元素(array)
- slice(start, len) 从数组的start位置删除len个元素,同时返回被删除的元素,而原数组不变
- concat(array) 在数组的后面接上一个数组array,同时返回拼接完成的数组,而原数组不变
从上面的各个方法中,我们能够看到,只能使用前面5个方法,最后2个方法不能修改原数组。因此现在的思路修改为:使用splice()
得到最后的k个元素,然后使用unshift()
把得到的数据一个个填充到数组的前面
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
var len, after;
len = nums.length;
k = k%len;
after = nums.splice(-k, k); // 得到最后k个元素
for(var i=k-1; i>=0 ;i--){
nums.unshift(after[i]); // 填充到数组的开始位置
}
};