javascript leetcode刷題筆記-coding pattern:Cyclic Sort

tags: leetcode algorithm worldpress

前言

最近開始整理以前刷過的leetcode題目，不出所料很多都沒有什麼印象得從頭再來XD 整理的過程中我開始用HackMD將每一題作比較完整的紀錄，其中包含題目說明、初步想法、虛擬碼以及最終提交的作法。 是個勞力活，不過說實在解題真的蠻有意思的，今天在整理的時候意外接觸到Cyclic Sort這樣的排序方法，覺得實在太有意思了，在此作個紀錄。 之後我會將整理完畢的leetcode筆記放上來，希望到時候能對也有在刷題的朋友有些幫助:D

什麼是Cyclic Sort? 為什麼我要用它?

Cyclic Sort 是一種coding pattern，在解決給定陣列僅含數字且在指定範圍內的題目時相當的實用，比起一般的sort()排序有著更好的時間複雜度(O(n))，且由於是in-place，不需要額外的記憶體空間，在空間複雜度的表現也相當良好(O(1))。核心概念相當的單純，就是根據元素的數字將它放置在對應的位置上，我們往下看個簡單的例子吧!

假設今天有一個陣列 [3, 1, 0, 2]
利用Cyclic Sort排序的概念大概是這樣的

step 1: 第一個元素3，它應該要在index = 3的位置，所以我們將它與index 3的元素互換
此時的陣列為 [2, 1, 0, 3]

step 2: 第一個元素2，它應該要在index = 2的位置，所以我們將它與index 2的元素互換
此時的陣列為 [0, 1, 2, 3]

step 3: 第一個元素0，它確實已經在index = 0的位置，所以我們繼續檢查下一個元素
此時的陣列為 [0, 1, 2, 3]

step 4: 第二個元素1，它確實已經在index = 1的位置，所以我們繼續檢查下一個元素
此時的陣列為 [0, 1, 2, 3]

step 5: 第三個元素2，它確實已經在index = 2的位置，所以我們繼續檢查下一個元素
此時的陣列為 [0, 1, 2, 3]

step 6: 第三個元素3，它確實已經在index = 3的位置，至此所有陣列元素檢查完畢，結束

在js中用程式碼會怎麼實現呢? 一樣用上方的例子吧! 我這邊寫個cyclicSort的函數

function cyclicSort(nums) {
  // 目前指向的元素
  let index = 0
  
  while (index < nums.length) {
    // 目前的元素應該要在的位置
    const targetIndex = nums[index]
    
    // 若目前元素不在該在的位置，與該位置的元素互換
    if (nums[index] !== nums[targetIndex]) {
      [nums[index], nums[targetIndex]] = [nums[targetIndex], nums[index]]
    } else {
      // 反之則往下一個元素看
      index++
    }
  }
  return nums
}

console.log(cyclicSort([3,1,0,2])) // [0, 1, 2, 3]

應用場景示範: leetcode#268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

解題思維

直接排序，然後找出index不對的那個即可。不過如果用sort在時間複雜度就出局了，題目很明確的說明數自從0->n，這是個使用Cyclic Sort的好時機，之後再跑一次迴圈找出位置不對的那個即可。

虛擬碼

宣告起始index
宣告result = 陣列長度(最終要做為回傳結果，假設位置都對的情況，缺少的就是陣列長度那一項)
while (index < 陣列長度) {
  若目前值位置不正確且該值小於陣列長度(等於陣列長度的值需要先忽略)
   交換nums[目前值]與nums[index]
  否則
    index++
}

for (i -> nums.length) {
    if (i !== nums[i]) return  i
}

return result

最終程式碼

var missingNumber = function(nums) {
    let i = 0
    let numsLenght = nums.length
    while (i < numsLenght) {
        const currentValue = nums[i]
        if (currentValue !== i & currentValue < nums.length) {
            [nums[currentValue],nums[i]] = [nums[i], nums[currentValue]]
        } else {
            i++
        }
    }
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] !== i) numsLenght =  i 
    }
    return numsLenght
};

結語

學會這樣的coding pattern在解題上確實很有幫助，就跟two pointer一樣，在面對特定情境的時候能提供你更多的思考選擇，裡面的邏輯需要花一點點時間消化，但我覺得這一點時間投資很划算:D 之後拿去應付一些找重複跟排重複的題目應該會比較有頭緒了!

參考文章

Coding Patterns: Cyclic Sort Leetcode 刷題 pattern – Cyclic Sort