Leetcode 邁向千題的關卡，想要把所有題目刷過一遍，對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難，因此想要將刷題常用的觀念技巧與其對應題目整理出來，一方面可以整理自己思緒，也可以做為未來複習用。
這系列文章會一直持續下去，算是作為工程師職涯的隨身裝備。

何謂 Cyclic Sort

題目給定一個 array ，如果 array 內部的數字都在一定範圍內， cyclic sort 可以在 in-place (not use any constant extra space) 且時間複雜度僅 O (n) 的條件下將 array 排序好。

Cyclic sort 作法為從 index 0 出發，依序檢查每個 index 的值，如果不屬於這個 index ，將他 swap 到正確的 index 上，以下圖為例，arr[0] 的值為 2 ，2 這個值應該被放到 index 2 的位置，因此我們將他與 arr[2] 的數進行 swap ，交換後 arr[0] 的值為 0 ，這個值確實屬於 index 0 ，因此可以繼續往後檢查下一個 index 上的值。

我覺得 cyclic sort 的威力在於，可以保證所走訪過的元素會被放到正確的 index 上。你可以實際對不同的 array 進行 cyclic sort ，你就能體驗我所說的 "保證所走訪過的數字會被放到正確的 index 上 "。

Cyclic Sort 操作框架

// input 為 vector<int>& nums ，且數字位在範圍 [0, size of array]
int size = nums.size();
int index = 0;

while (index<size)
{
    int element = nums[index];
    /**
     * 如果 element 並不應該位在當前的 index 上，
     * 就將它 swap 到他應該在的 index
     */
    if (element >= 0 && element < size
            && nums[index] != nums[element])
    {
        std::swap (nums[element], nums[index]);
    }
    else
        index++;
}

何時使用

1. 題目 input 為一個 array ，資料在特定的範圍內 ( 例如 1 ~ size of array )
2. 如果題目要求在 array 中找 missing / duplicate / smallest 的 number

接下來我們來看幾個例題，了解這類題目如何變化？

Leetcode #442 Find All Duplicates in an Array

題目告訴你 array 內的值會在 1 ~ size of array ，請你找出 array 內重複出現的數字？

看到這樣的條件，就可以聯想到使用 cyclic sort ，透過 cyclic sort 排序後，只要 index 上的值不等於該 index ，可以代表這個值必定是重複出現的數字。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int size = nums.size ();
        int index = 0;

        while (index < size)
        {
            /**
             *  由於 array 的值是從 1 到 size of array ，
             *  為了與 index 可以對齊，將 array 的值減 1 來對齊
             */
            int element = nums[index]-1;
            if (index >= 1 && index < size
                && nums[index] != nums[element])
            {
                std::swap (nums[index], nums[element]);
            }
            else
                index++;

        }
        vector<int> result;
        for (int i=0; i<size; i++)
        {
            if (nums[i] != i+1)
            {
                result.push_back (nums[i]);
            }
        }
        return result;
    }
};

延伸題目

Leetcode #268, #448

Leetcode #41 First Missing Positive

這題雖然 input 並沒有在特定範圍內，但是他要求要在 O(n) 時間且耗費 constant space 來找到第一個消失的正數，這樣的條件下可以使用 cyclic sort 達成。

具體程式碼如下，有兩個點需要注意，

1. 由於 input 沒有被侷限在特定範圍內，但我們只關心 index 內的元素，因此如果 value 不在 index 範圍內，我們一律忽視。
2. 需要處理 edge case ，例如 value 等於 INT_MIN ，由於會對 value 減 1 ，即可能發生 overflow 的狀況。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int size = nums.size();
        if (size == 0)
            return 1;
        int index = 0;

    while (index < size)
    {
        /**
         * Consider the case that value is INT_MIN,
         * overflow happens when it was substracted by 1.
         */
        if (nums[index] == INT_MIN)
        {
            index++;
            continue;
        }
        int element_val = nums[index]-1;
        if (element_val >= 0 && element_val < size 
            && nums[index] != nums[element_val]) 
        {
            std::swap (nums[index], nums[element_val]);
        }
        else
        {
            index++;
        }
    }

    for (int i=0; i<size; i++)
    {
        if (nums[i] != i+1)
        {
            return i+1;
        }
    }
    return size+1;
    }
};

時間複雜度

一般要將一個 array 需要排序，第一時間一定想到可以選擇某一種 sorting algorithm 來排序，其時間複雜度至少需要 O (n log n) ，但是透過 Cyclic Sort ，其時間複雜度僅為 O (n-1) + O (n) ，最多會發生 n-1 次的 swap ，n-1 個 index 上的數字就被確定，剩下的第 n 個數字當然也會再正確的位置上；而 O (n) 則是發生在 index 的遞增上。

Reference

1. Leetcode 刷題 pattern - Cyclic Sort
2. Coding Patterns: Cyclic Sort
3. 14 Patterns to Ace Any Coding Interview Question

Updated on 2021-07-03 08:51:46 星期六