亲宝软件园·资讯

展开

JavaScript数组旋转k步

有出路 人气:1

一、题目描述:

将一个数组旋转k步

二、思路分析:

两种思路:

思路1:把末尾的元素挨个pop,然后unshift到数组后面

删除数组的最后一个元素:

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.pop();

将新项目添加到数组的开头:

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.unshift("Lemon","Pineapple");

TS代码

function rotate1(arr:number[],k:number):number[]{
    const length = arr.length
    if(!k||length===0)return arr
    const step = Math.abs(k%length)

    for(let i =0;i<step;i++){
        const n = arr.pop()
        if(n){
            arr.unshift(n)
        }
    }
    return arr
}
const arr = [1,2,3,4,5,6,7,8]
const arr1 = rotate1(arr,3)
console.log(arr1)

运行结果

思路2:把数组拆分,最后concat拼接到一起

JavaScript Array slice() 方法

var fruits = ["Banana", "Orange", "Lemon", "Apple", "Mango"];
var citrus = fruits.slice(1, 3);

JavaScript 数组 Const

const array1 = ['a', 'b', 'c'];
const array2 = ['d', 'e', 'f'];
const array3 = array1.concat(array2);

console.log(array3);
// expected output: Array ["a", "b", "c", "d", "e", "f"]

TS代码

/**
 * 旋转数组K步 -使用concat
 * @param arr arr 
 * @param k k 
 * @returns arr
 */
function rotate2(arr:number[],k:number):number[]{
    const length = arr.length
    if(!k || length===0) return arr
    const step = Math.abs(k%length)

    const part1 = arr.splice(-step)
    const part2 = arr.splice(0,length-step)
    arr = arr.concat(part1,part2)
    return arr   
}
const arr2 = [1,2,3,4,5,6,7,8]
const arr3 = rotate2(arr2,3)

console.log(arr3)

运行结果

三、总结:

分析代码,整理思路,尽量找出最优解,编写代码不仅要书写功能测试,而且要养成编写单元测试的习惯,保证程序的健壮性

复杂度分析:

  • 思路1的时间复杂度为O(n^2),空间复杂度为O(1)
  • 思路2的时间复杂度为O(1),空间复杂度为O(n)

前端重时间轻空间,思路2更佳

时间复杂度O(1)和O(n)差别很大

5. 数组是一个有序结构,数组的unshift、shirt、splice操作都很慢,pop和push都很快,.slice不会改变原数组,时间复杂度为0(1)

//性能测试
const arr4 = []
for(let i =0;i<10 * 10000;i++){
    arr4.push(i)
}
console.time('rotate1')
rotate1(arr4,9*10000)
console.timeEnd('rotate1')

const arr5 = []
for(let i=0;i< 10 * 10000;i++){
    arr5.push(i)
}
console.time('rotate2')
    rotate2(arr5,9*10000)
    console.timeEnd('rotate2')

四、划重点

加载全部内容

相关教程
猜你喜欢
用户评论