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

Posted on by

一、題目描述：

將一個數組旋轉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！

推薦閱讀：