JavaScript算法題之如何將一個(gè)數(shù)組旋轉(zhuǎn)k步
一、題目描述:
將一個(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ù)組后面
- JavaScript Array pop() 方法
刪除數(shù)組的最后一個(gè)元素:
var fruits = ["Banana", "Orange", "Apple", "Mango"]; fruits.pop();
- JavaScript Array unshift() 方法
將新項(xiàng)目添加到數(shù)組的開頭:
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)
運(yùn)行結(jié)果
思路2:把數(shù)組拆分,最后concat拼接到一起
JavaScript Array slice() 方法
var fruits = ["Banana", "Orange", "Lemon", "Apple", "Mango"]; var citrus = fruits.slice(1, 3);
JavaScript 數(shù)組 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代碼
/** * 旋轉(zhuǎn)數(shù)組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)
運(yùn)行結(jié)果
三、總結(jié):
分析代碼,整理思路,盡量找出最優(yōu)解,編寫代碼不僅要書寫功能測(cè)試,而且要養(yǎng)成編寫單元測(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è)試 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')
四、劃重點(diǎn)
- 注意算法時(shí)間復(fù)雜度(前端重時(shí)間,輕空間)
- 識(shí)破內(nèi)置API的時(shí)間復(fù)雜度(如unshift為0(n))
- 單元測(cè)試,考慮參數(shù)非法情況,提升代碼健壯性
到此這篇關(guān)于JavaScript算法題之如何將一個(gè)數(shù)組旋轉(zhuǎn)k步的文章就介紹到這了,更多相關(guān)JavaScript數(shù)組旋轉(zhuǎn)k步內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
JS+HTML5 Canvas實(shí)現(xiàn)簡(jiǎn)單的寫字板功能示例
這篇文章主要介紹了JS+HTML5 Canvas實(shí)現(xiàn)簡(jiǎn)單的寫字板功能,結(jié)合實(shí)例形式分析了js結(jié)合HTML5 canvas特性的圖形繪制相關(guān)操作技巧,需要的朋友可以參考下2018-08-08JavaScript版DateAdd和DateDiff函數(shù)代碼
VBScript中有兩個(gè)非常好用的日期操作函數(shù):DateAdd用來給日期添加指定時(shí)間間隔,DateDiff用來返回兩個(gè)日期的時(shí)間間隔。可惜的是JavaScript沒有,不過我們可以寫一個(gè)函數(shù)來實(shí)現(xiàn),一樣的,呵呵2012-03-03js apply/call/caller/callee/bind使用方法與區(qū)別分析
js apply/call/caller/callee/bind使用方法與區(qū)別分析,需要的朋友可以參考下。2009-10-10JavaScript實(shí)現(xiàn)煙花綻放動(dòng)畫效果
這篇文章主要介紹了JavaScript如何實(shí)現(xiàn)煙花綻放動(dòng)畫效果,文中講解非常細(xì)致,代碼幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下2020-08-08詳解釘釘小程序組件之自定義模態(tài)框(彈窗封裝實(shí)現(xiàn))
這篇文章主要介紹了釘釘小程序組件之自定義模態(tài)框(彈窗封裝實(shí)現(xiàn))的相關(guān)知識(shí),本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-03-03Function.prototype.call.apply結(jié)合用法分析示例
昨天在網(wǎng)上看到一個(gè)很有意思的js面試題:var a = Function.prototype.call.apply(function(a){return a;}, [0,4,3]);alert(a); 分析步驟如下,感興趣的朋友可以參考下哈2013-07-07無循環(huán) JavaScript(map、reduce、filter和find)
本文由淺入深地介紹了map、reduce、filter和find函數(shù),如何一步一步把循環(huán)從代碼中抽離掉2017-04-04