leetcode-rotate-array

蚊子前端博客
发布于 2015-04-19 06:00
这是leetcode的一道算法题目,主要是讲解数组的旋转

这是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进行编程时,里面有个提示非常的重要:

COPYJAVASCRIPT

>/** * @param {number[]} nums * @param {number} k * @return {void} Do not return anything, modify nums in-place instead. */

如果用JavaScript的话,那么你的程序必须是:不用返回任何数据,而且,只能修改nums,不能替换nums的数据,比如:nums=***

刚开始没有注意到这句话,就想着,把最后k个数获取到,然后跟剩余的拼接起来,并赋值给nums即可。于是就产生了下面的程序:

COPYJAVASCRIPT

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()把得到的数据一个个填充到数组的前面

COPYJAVASCRIPT

/** * @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]); // 填充到数组的开始位置 } };
标签:
阅读(263) 评论(0)

公众号:

qrcode

微信公众号:前端小茶馆