JavaScript算法題之如何將一個(gè)數(shù)組旋轉(zhuǎn)k步

第JavaScript算法題之如何將一個(gè)數(shù)組旋轉(zhuǎn)k步目錄一、題目描述：二、思路分析：兩種思路：思路1：把末尾的元素挨個(gè)pop，然后unshift到數(shù)組后面TS代碼運(yùn)行結(jié)果思路2：把數(shù)組拆分，最后concat拼接到一起TS代碼運(yùn)行結(jié)果三、總結(jié)：四、劃重點(diǎn)

一、題目描述：

將一個(gè)數(shù)組旋轉(zhuǎn)k步

輸入一個(gè)數(shù)組[1,2,3,4,5,6,7,8]當(dāng)k=3時(shí)，即旋轉(zhuǎn)3步輸出[6,7,8,1,2,3,4,5]

二、思路分析：

兩種思路：

把末尾的元素挨個(gè)pop，然后unshift到數(shù)組后面把數(shù)組拆分，最后concat拼接到一起

思路1：把末尾的元素挨個(gè)pop，然后unshift到數(shù)組后面

JavaScriptArraypop()方法

刪除數(shù)組的最后一個(gè)元素：

varfruits=["Banana","Orange","Apple","Mango"];

fruits.pop();

JavaScriptArrayunshift()方法

將新項(xiàng)目添加到數(shù)組的開(kāi)頭：

varfruits=["Banana","Orange","Apple","Mango"];

fruits.unshift("Lemon","Pineapple");

TS代碼

functionrotate1(arr:number[],k:number):number[]{

constlength=arr.length

if(!k||length===0)returnarr

conststep=Math.abs(k%length)

for(leti=0;istep;i++){

constn=arr.pop()

if(n){

arr.unshift(n)

returnarr

constarr=[1,2,3,4,5,6,7,8]

constarr1=rotate1(arr,3)

console.log(arr1)

運(yùn)行結(jié)果

思路2：把數(shù)組拆分，最后concat拼接到一起

JavaScriptArrayslice()方法

varfruits=["Banana","Orange","Lemon","Apple","Mango"];

varcitrus=fruits.slice(1,3);

JavaScript數(shù)組Const

constarray1=['a','b','c'];

constarray2=['d','e','f'];

constarray3=array1.concat(array2);

console.log(array3);

//expectedoutput:Array["a","b","c","d","e","f"]

/**

*旋轉(zhuǎn)數(shù)組K步-使用concat

*@paramarrarr

*@paramkk

*@returnsarr

functionrotate2(arr:number[],k:number):number[]{

constlength=arr.length

if(!k||length===0)returnarr

conststep=Math.abs(k%length)

constpart1=arr.splice(-step)

constpart2=arr.splice(0,length-step)

arr=arr.concat(part1,part2)

returnarr

constarr2=[1,2,3,4,5,6,7,8]

constarr3=rotate2(arr2,3)

console.log(arr3)

三、總結(jié)：

分析代碼，整理思路，盡量找出最優(yōu)解，編寫(xiě)代碼不僅要書(shū)寫(xiě)功能測(cè)試，而且要養(yǎng)成編寫(xiě)單元測(cè)試的習(xí)慣，保證程序的健壯性

復(fù)雜度分析：

思路1的時(shí)間復(fù)雜度為O(n^2),空間復(fù)雜度為O(1)思路2的時(shí)間復(fù)雜度為O(1),空間復(fù)雜度為O(n)

前端重時(shí)間輕空間，思路2更佳

時(shí)間復(fù)雜度O(1)和O(n)差別很大

5.數(shù)組是一個(gè)有序結(jié)構(gòu)，數(shù)組的unshift、shirt、splice操作都很慢，pop和push都很快，.slice不會(huì)改變?cè)瓟?shù)組，時(shí)間復(fù)雜度為0（1）

//性能測(cè)試

constarr4=[]

for(leti=0;i10*10000;i++){

arr4.push(i)

console.time('rotate1')

rotate1(arr4,9*10000)

console.timeEnd('rotate1')

constarr5=[]

for(leti=0;i10*10000;i++){

arr5.push(i)

console.time('rotate2')

rotate2(arr5,9*10000)