JavaScript算法題之如何將一個數組旋轉k步

一、題目描述:

將一個數組旋轉k步

  • 輸入一個數組[1,2,3,4,5,6,7,8]
  • 當k=3時,即旋轉3步
  • 輸出[6,7,8,1,2,3,4,5]

二、思路分析:

兩種思路:

  • 把末尾的元素挨個pop,然後unshift到數組後面
  • 把數組拆分,最後concat拼接到一起

思路1:把末尾的元素挨個pop,然後unshift到數組後面

  • JavaScript Array pop() 方法

刪除數組的最後一個元素:

var fruits = ["Banana", "Orange", "Apple", "Mango"];
fruits.pop();
  • JavaScript Array unshift() 方法

將新項目添加到數組的開頭:

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')

四、劃重點

  • 註意算法時間復雜度(前端重時間,輕空間)
  • 識破內置API的時間復雜度(如unshift為0(n))
  • 單元測試,考慮參數非法情況,提升代碼健壯性

到此這篇關於JavaScript算法題之如何將一個數組旋轉k步的文章就介紹到這瞭,更多相關JavaScript數組旋轉k步內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: