Leetcode 刷題 pattern - Cyclic Sort

前言

身在大 CS 時代，有越來越多人投入刷題的行列，在眼花撩亂的題海中，要想有效率地刷題，就需要掌握題目解法中，可以在許多地方應用的觀念，才能以簡禦繁。 Huli 寫的 程式解題新手入門注意事項 和 當我們在學程式時，要學的到底是什麼？ 講得很好，寫題目是為了學會解題的思考法，確保自己掌握重要的資料結構跟演算法。這也是我寫這系列文章的原因，我想把多個散落在各處的題目銜接起來，以後看到相似的問題就可以舉一反三，而不是去背各題目的解法。

舉例來說，最近有個朋友遇過一題面試題，問到的題目是：

input是一串 01 組成的字串(長度不固定) e.g. 01011，從同樣長度的00000 翻轉成 01011，最少要幾次反轉？
其中翻轉這個操作只能從某個 index 翻轉到最後一位，
例如 00000，若翻轉 index 0 就變成 11111；
若翻轉 index 1 就變成 01111。

範例：
input = 01011 
output = 3 

從 00000 開始，第一次翻 index 1，得到 01111；
第二次翻 index 2，得到 01000；
第三次翻 index 3，就得到目標的 01011。

因為學過 BFS 的 pattern，所以朋友問我這題，直覺上就想到要用 BFS，也很快就寫出一個解答。這個例子也明確地展示，不需要把題目都刷完，而是要掌握解題的思維，接下來應用這些思維就可以解很多變化題。

放上 C++ 程式碼給大家參考：

#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>

using namespace std;

string flipFromIndex(string bits, int index) {
    for(int i = index; i < bits.length(); ++i) {
        bits[i] = (bits[i] == '1') ? '0' : '1';
    }

    return bits;
}

int minFlipsTowardByBFS(string start, string goal) {
    // Init for BFS
    queue<string> q;
    unordered_set<string> visited;

    q.push(start);
    visited.insert(start);

    // Start BFS
    int step = 0;
    while(!q.empty()) {
        for(int i = q.size() - 1; i >= 0; --i) {
            string cur = q.front();
            q.pop();

            if(cur == goal) {
                return step;
            }

            for(int j = 0; j < cur.length(); ++j) {
                string tmp = flipFromIndex(cur, j);

                if(!visited.count(tmp)) {
                    q.push(tmp);
                    visited.insert(tmp);
                }
            }
        }

        ++step;
    }
}

int main() {
    string start = "00000", goal = "01011";
    int min_steps_bfs = minFlipsTowardByBFS(start, goal);

    cout << min_steps_bfs << " steps needed to convert " 
         << start << " to " << goal << endl;

    return 0;
}

好啦，接下來就讓我們開始今天的正題吧！

Cyclic Sort 簡介

Cyclic Sort 是一個相對簡單的 pattern，他的應用場景是，給定一個 array 跟 array 中 element 的範圍。在這個情況下，就可以用 cyclic sort 來有效率地把 array 中的 element sort 到對的位置上。

讓我們來看一個範例：

input: [1,2,0]，且已知 array 中的 element 就是從 0 ~ array.size()-1
output: [0,1,2]

這個問題，我們可以用任意一個較佳的 sort 演算法在 O(nlogn) 的時間複雜度內完成。不過，既然我們已經知道這個 array 中 element 的範圍，就應該好好利用這個資訊。

以上面的例子來說，當我們看到：

array: [1,2,0]
        ^

Step 1: 看到 1 時，我們知道 1 應該要放在 index 1，檢查 1 != array[1] 
我們就把 1 跟 array[1] 互換，這時 array 變成

array: [2,1,0]

Step 2: 看到 2 時，我們知道 2 應該要放在 index 2，檢查 2 != array[2] 
我們就把 2 跟 array[2] 互換，這時 array 變成

array: [0,1,2]

Step 3: 看到 0 時，我們知道 0 應該要放在 index 0，檢查 0 == array[0]，我們就往下檢查
Step 4: 看到 1 時，我們知道 1 應該要放在 index 1，檢查 1 == array[1]，我們就往下檢查
Step 5: 看到 2 時，我們知道 2 應該要放在 index 2，檢查 2 == array[2]，結束

接下來把上面的概念寫成 code：

#include <iostream>
#include <vector>

using namespace std;

void cyclic_sort(vector<int>& nums) {
    int i = 0, n = nums.size();

    while(i < n){
        int j = nums[i];

        if(j < n and nums[i] != nums[j]) {
            swap(nums[i], nums[j]);
        }
        else{
            ++i;
        }
    }
}

int main() {
    vector<int> nums = {1,2,0};
    cyclic_sort(nums);

    cout << "Sorted array: [ ";
    for(auto& n: nums)
        cout << n << " ";
    cout << "].\n";

    return 0;
}

以上就是 Cyclic Sort 的基本概念。這時你可能會有個疑問，這樣真的有比 O(nlogn) 快嗎？

答案是有的，因為每次 swap 都會確保有一個 element 被放對位置，所以最多只需要 n-1 次 swap（經過 n-1 次 swap，第 n 個 element 也會在對的位置，如果你覺得有點不通透，可以從上面的例子觀察得到）；加上有時候不會 swap，最多需要 increment i n 次，所以時間複雜度會是 O(n-1) + O(n)，所以還是 O(n) 的時間複雜度。

Cyclic Sort 的第一個範例 - Leetcode #268 - Missing Number

題目

Cyclic Sort 解法

這題算是很標準的 cyclic sort，理論上如果你學懂了上面 Cyclic Sort 簡介的部分，這題你可以試著自己解解看，確保自己了解 swap、++i 這邊的邏輯，再繼續往下看。

這題的方法是，先做完 cyclic sort，然後再走過一次 array，看哪個 index 跟 array[index] 不一致，就找到答案了。所以只花了 constant space，並且在 O(n) 時間內就可以解決。實作如下：

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n){
            int j = nums[i];

            if(j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else{
                ++i;
            }
        }

        // Find the first wrong number
        int missed = n; // when we have case like this: [0], ans should be 1
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i) {
                missed = i;
                break;
            }
        }

        return missed;
    }
};

Cyclic Sort 的第二個範例 - Leetcode #448 - Find All Numbers Disappeared in an Array

題目

我們可以看到題目中的關鍵句 - Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array)，這時就可以直覺地想想看是否可以用 cyclic sort 來解決這個問題。

Cyclic Sort 解法

雖然這題可能有多個 duplicate，但我們還是可以先用 cyclic sort 把對的 element 放到對的 index，剩下不管是單獨多出來的還是 duplicate 的，都會被放在 missing element 的地方。所以只要再走過一次 cyclic sort 完的 array，並把跟 index 不合的所有 element 都放入答案就好。

程式碼如下：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            int j = nums[i] - 1;
            if(j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else {
                ++i;
            }
        }

        // Find all missing number 
        vector<int> missed;
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                missed.push_back(i + 1);
            }
        }

        return missed;
    }
};

Index as hash key 解法

感謝 @陳冠綸 在 Facebook 留言提出不同的想法，花了我一些時間才想懂。這個解法可以省去 swap 操作的時間，主要的概念是，先走過一次 input array，把已經出現過的 index element 變成負的，然後再走過一次 array，就可以看哪些 element 還是正數，就知道那些 element 所在 index 不曾出現過。

我們可以用題目裡的範例來過一次這個演算法：

Input： [4, 3, 2, 7, 8, 2, 3, 1] 

我們把 input 中每個 element 都減 1，就得到了 index array [3, 2, 1, 6, 7, 1, 2, 0]，這個 array 表示 input 中的每個 element 應該要在哪個 index 出現 

接下來我們依序走過 array，把已經看過的 index 標成負的
1. i = 0， 把 nums[3] 變成負的， nums 變成 [4, 3, 2, -7, 8, 2, 3, 1]
2. i = 1， 把 nums[2] 變成負的， nums 變成 [4, 3, -2, -7, 8, 2, 3, 1]
3. i = 2， 把 nums[1] 變成負的， nums 變成 [4, -3, -2, -7, 8, 2, 3, 1]
4. i = 3， 把 nums[6] 變成負的， nums 變成 [4, -3, -2, -7, 8, 2, -3, 1]
5. i = 4， 把 nums[7] 變成負的， nums 變成 [4, -3, -2, -7, 8, 2, -3, -1]
6. i = 5， 把 nums[1] 變成負的， 因為在 i == 2 的時候，已經把 nums[1] 變成負的了，表示這個 index 出現過，所以這次不變
7. i = 6， 把 nums[2] 變成負的， 因為在 i == 1 的時候，已經把 nums[2] 變成負的了，表示這個 index 出現過，所以這次不變
8. i = 7， 把 nums[0] 變成負的， nums 變成 [-4, -3, -2, -7, 8, 2, -3, -1]

接下來，我們再掃一次 nums，
發現 nums[4] = 8 跟 nums[5] = 2 都 > 0，
所以 4 & 5 並沒有在 index array 中出現，
表示 5 & 6 不在原本的 input 裡面。

實作如下：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        // Use negative to mark this index has appeared
        for(int i = 0; i < nums.size(); ++i) {
            int idx = abs(nums[i]) - 1;

            if(nums[idx] > 0) {
                nums[idx] *= -1;
            }
        }

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

        return res;
    }
};

這個範例有兩層意義：

1. 對於刷題還不夠熟的讀者，先學習 pattern 可以幫助你用一招半式打下很多題，但也可能會障礙你追逐最佳解的意識
2. 所以對於刷題已經到一定程度，對 pattern 也有一些了解的讀者，應該要開始跳脱 pattern，思考最佳解

Cyclic Sort 的第三個範例 - Leetcode #442 - Find All Duplicates in an Array

題目

這題本身難的點只在於題目要求 Could you do it without extra space and in O(n) runtime?

這就是 cyclic sort 好用的地方。

Cyclic Sort 解法

這題其實跟上一個範例有點像，雖然會有多個 element 有 duplicate，我們還是可以先做 cyclic sort，再看哪些 element 跟 index 對應不起來。另外因為只會有最多一個 duplicate，所以直接把跟 index 對應不起來的 element 放到 result 裡就好，而不需要擔心會不會放重複的 element 進 result。實作如下：

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            int j = nums[i] - 1;
            if(nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else {
                ++i;
            }
        }

        // Get the duplicates
        vector<int> duplicate;

        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                duplicate.push_back(nums[i]);
            }
        }

        return duplicate;
    }
};

Cyclic Sort 的第四個範例 - Leetcode #41 - First Missing Positive

題目

這題如果不會 cyclci sort，個人覺得還滿難的，大家也可以自己嘗試解解看。

Cyclic Sort 解法

如果會 cyclic sort，只要先做完 cyclic sort，第一個跟 index 對不上的地方就是 missing 的 positive，實作如下：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.empty()) {
            return 1;
        }

        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            int j = nums[i] - 1;

            if(j >= 0 and j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else{
                ++i;
            }
        }

        // Find the first idx not matching with nums[idx]
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

但以上的解法無法通過 Leetcode 的所有 test case！例如：nums =[2147483647,2147483646,2147483645,3,2,1,-1,0,-2147483648]

因為我們在算 nums[i] 的正確 index j 時，我們是用 int j = nums[i] - 1;，所以若 nums[i] == INT_MIN 時，就會 overflow。這體現了題目要盡量問清楚，也要先討論好極端的 corner case，再開始實作。以下才是可以通過 Leetcode 所有 test case 的版本。

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.empty()) {
            return 1;
        }

        // Cyclic sort
        int i = 0, n = nums.size();
        while(i < n) {
            if(nums[i] == INT_MIN) {
                ++i;
                continue;
            }
            int j = nums[i] - 1;

            if(j >= 0 and j < n and nums[i] != nums[j]) {
                swap(nums[i], nums[j]);
            }
            else{
                ++i;
            }
        }

        // Find the first idx not matching with nums[idx]
        for(int i = 0; i < n; ++i) {
            if(nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
};

總結

今天跟大家介紹了一個新的 pattern - Cyclic Sort，上面提供的幾題是讓大家體驗一下用這個 pattern 的好處。相對於其他 pattern，它的變化比較少，但如果你對這個 pattern 不熟，在面試時遇到最後一個範例那種題目，要在時間限制內想出最佳解也不太容易。當然刷題不只是為了通過面試，而是加強自己對資結和演算法的洞見和體驗，進而優雅有效率地解決問題，共勉之。

延伸閱讀

1. Leetcode 刷題 pattern - Two Pointer
2. Leetcode 刷題 pattern - Sliding Window
3. Leetcode 刷題 pattern - Next Greater Element
4. Leetcode 刷題 pattern - Fast & Slow Pointer
5. Leetcode 刷題 pattern - Breadth-First Search
6. Leetcode 刷題 pattern - Merge Intervals

關於作者：
@pojenlai 演算法工程師，對機器人、電腦視覺和人工智慧有少許研究，正致力改善 自己的習慣。