1.3解题思路
在不使用额外数组的前提下,我们可以有如下思考,
设数组长度为length,则
-
需要轮转k位,即数组的最后k位会进行挪移至数组前方,即,当我们反转数组后,可以得知[0,k-1],[k,lenth-1]这两个数组,即为轮转之后的对应数组,但是,两个数组中的元素排序是反的;
-
接下来,依次反转[0,k-1],[k,lenth-1],这两个数组,得到的数组就是答案了
1.4 代码
const reverseArray = (nums, start, end) => {
while (start < end) {
const temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
return nums;
var reverseFunction = function(nums, k) {
let length = nums.length;
nums = reverseArray(nums, 0, length - 1);
nums = reverseArray(nums, 0, k - 1);
nums = reverseArray(nums, k, length - 1);
reverseFunction([1,2,3,4,5,6,7],3);
输出:[5,6,7,1,2,3,4]
1.5 复杂度分析
- 时间复杂度:时间复杂度:O(n),其中 nn 为数组的长度。每个元素被翻转两次,一共 n 个元素,因此总时间复杂度为 O(2n)=O(n)。
- 空间复杂度:O(1)。只需要常数空间存放若干变量。
1.6 其他解法
- 思路:
- 既然轮转k位,即[length-1-k,length-1]位置的元素变为[0,k-1]
- [0,length-1-k]位置的元素变为[length-1-k,length-1]
- 所以我们只需要将原数组拆分为[0,k-1],[length-1-k,length-1],然后将其按照[length-1-k,length-1]+[0,k-1]组装成一个数组即可
var reverseFunction2 = function(nums, k) {
let length = nums.length;
let arrayLeft = nums.slice(0,length-k);
let arrayRight = nums.slice(length-k);
return arrayRight.concat(arrayLeft);
reverseFunction2([1,2,3,4,5,6,7],3);
大家会发现上述代码中,我注释了一行,因为,绝对诱人会想使用new Set方法去合并两个数组,那么,请注意,千万不能使用,因为,new Set方法,会讲两个数组进行合并后去重,如果原数组中出现相同元素,则,new Set将会给使用者狠狠上一课!
算法的逻辑不同的人有不同的想法,但是殊途同归,答案是一致的,前提是,一定要靠清楚问题,仔细分析,验证的时候也要考虑各种情况。
算法的验证,必要且一定,好的算法,少不了单元测试
web前端面试高频考点——Vue原理(diff算法、模板编译、组件渲染和更新、JS实现路由)
web前端面试高频考点——Vue原理(diff算法、模板编译、组件渲染和更新、JS实现路由)