CS:APP 全名為 Computer Systems: A Programmer’s Perspective，是 CMU 計算機概論課程的教材。
根據 jserv 老師的說法，這們課等同台灣研究所課程的難度，希望大家認真讀這本教材後，能夠有國外頂尖大學大二學生的程度。隨著電腦科技發展日新月異，最基礎的學科仍舊是所有新技術的根基，與其不斷追求新技術，不如好好打穩根基，因此決定研讀這本教科書，搭配 CMU 的課程講義與影片，還有 jserv 老師的補充資料一同學習，期許自己能夠對資訊科技有扎實的基礎。

共筆連結

我將筆記寫於 hackmd ，方便所有朋友發現任何錯誤都可以直接修正，我也同步把筆記發表於 CS:APP Taiwan study group ，歡迎一起來讀書討論！

CH2 Presentation and Maipulating Information

(推薦必讀，對於程式碼會有更深刻的認知！)
共筆連結

CH3 Machine-level Representation of Programs

共筆連結

CH7 Linking

共筆連結

參考資料

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

如何辨識 Top K element 類型題目

題目給你一組資料，要你找出 top / smallest / frequent 的 K 筆資料。這類型題目很好分辨，在 Leetcode 上的統計，這類型題目出現在面試的頻率都相當高，通常有三種解法：

暴力解
使用 Heap
Quick Select

Leetcode #973 K Closest Points to Origin

題目敘述:
平面上有多個點，問你最靠近原點的 K 個點是哪些?

方法 1 Sorting

計算每點與原點的距離，再對所有距離排序，並將前 K 個點作為答案。這是最直覺的解法，但其時間複雜度為 O (N log N) ，空間複雜度 O(1)。

class Solution {
private:
    static bool comp (vector<int> a, vector<int> b)
    {
        return a[0]*a[0] + a[1]*a[1] <
            b[0]*b[0] + b[1]*b[1];
    }
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        std::sort (points.begin(),
            points.end(), comp);
        return vector<vector<int>> (points.begin(),
                                points.begin()+K);
    }
};

方法 2-1 MinHeap

使用 MinHeap 存放所有 element ，再將 heap 的前 K 個元素 pop 出來
時間複雜度為 O (N+ K log N) ，其中 O(N) 為製作 priority queue 的時間，每次由 priority queue 刪除元素要 O (log N) 時間。
空間複雜度 O(N)

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, 
                                int K) {
        priority_queue<vector<int>,
            vector<vector<int>>, heap_compare> 
            pq (points.begin(), points.end());

        vector<vector<int>> result;
        for (int i=0; i<K; i++)
        {
            result.push_back (pq.top());
            pq.pop();
        }
        return result;
    }
private:
    struct heap_compare {
        bool operator () (const vector<int> p1,
                          const vector<int> p2)
        {
            return (p1[0]*p1[0])+(p1[1]*p1[1]) >
                (p2[0]*p2[0])+(p2[1]*p2[1]);
        }
    };
};

方法 2-2 MaxHeap

題目只要找前 K 小的，後面更大元素都不需要保留，使用 MaxHeap 存放 k 個較小的 element ，每新增一個 element 到 heap ，需耗費 O (log K)，只要 MaxHeap 的大小超過 K ，就刪除元素，需耗費 O (log K) ，全部時間複雜度為 O (N log K) 。

空間複雜度 O(K) 。

class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
    priority_queue< pair<vector<int>, int>,
        vector<pair<vector<int>, int>>,
        heap_compare> pq;

    for (auto point:points)
    {
        int dis = (point[0]*point[0]) 
                + (point[1]*point[1]);
        pq.push (make_pair(point, dis));
        if (pq.size() > K)
        {
            pq.pop();
        }
    }

    vector<vector<int>> result;
    for (int i=0; i<K; i++)
    {
        result.push_back (pq.top().first);
        pq.pop();
    }
    return result;
}
private:
struct heap_compare {
    bool operator () (const pair<vector<int>, int> p1,
                      const pair<vector<int>, int> p2)
    {
        /*
         *The larger element will be put
         * on the larger index
         */
        return p1.second < p2.second;
    }
};
};

方法 3 Quick Select

如果想要比 O(N logN) 更快的方法，可以利用題目說的 "K elements 可以被以任意順序回傳" ，否則做了 sorting 後，至少都需要 O(N logN) 。
Quick select 一般用於解決 Kth element 的問題， average case 下可以在 O(n) 時間複雜度下完成，worst case 會到 O(n^2) ，可以藉由打亂 array 來盡可能避免 worst case 狀況發生，O(1) 空間複雜度完成。
quick select 可以說是 quick sort 的簡化。 quick sort 會選擇 pivot 並將整個 array 劃為兩邊，接著再以同樣方式處理兩邊資料。但這題要找 Kth element ，並不需要將整個 array 排序，只需找到第 K 大作為 pivot ，將比他小的與比他大的元素分到兩邊即可。

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points,
                                    int K) {
        quickSelect (points, K);
        return vector<vector<int>> (points.begin(),
                                    points.begin() + K);
    }
    bool comp (vector<int> a, vector<int> b)
    {
        return a[0]*a[0] + a[1]*a[1] <
            b[0]*b[0] + b[1]*b[1];
    }

    int partition (vector<vector<int>>& points, 
        int left, int right)
    {
        int shuffle = (rand()%(right-left+1)) + left;
        std::swap (points[right], points[shuffle]);
        int store_index = left;

        for (int i=left; i<right; i++)
        {
            if (comp (points[i], points[right]))
            {
                std::swap (points[i], points[store_index]);
                store_index++;
            }
        }
        std::swap (points[store_index], points[right]);
        return store_index;
    }
    void quickSelect (vector<vector<int>>& points, int k)
    {
        int left = 0, right = points.size()-1;
        while (right > left)
        {
            int pos = partition (points, left, right);
            if (pos == k)
            {
                return;
            }
            else if (pos < k)
            {
                left = pos+1;
            }
            else
            {
                right = pos-1;
            }
        }
    }
};

Leetcode #347 Top K Frequent Elements

方法 1

統計每個 element 出現次數並存到 unordered_map ，請不要對 unordered_map 直接做排序（可參考 stackoverflow 上討論），接著轉存放到 vector 並排序，再挑出前 K 個大的即可。
時間複雜度為 O (N logN) ，空間複雜度為 O (N) 。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> intDict;
        for (auto num:nums)
        {
            intDict[num]++;
        }
        vector<pair<int,int>> int_arr;
        for (auto intFreq:intDict)
        {
            int_arr.push_back (intFreq);
        }
        sort (int_arr.begin(), int_arr.end(), comp);

        vector<int> result;
        for (int i=0; i<k; i++)
        {
            result.push_back (int_arr[i].first);
        }
        return result;
    }
private:
    static bool comp (pair<int, int> p, pair<int, int> q)
    {
        return p.second > q.second;
    }
};

方法 2-1 MinHeap

跟上一題一樣的模板，製造一個 MinHeap ，時間複雜度為 O (N + K log N)，空間複雜度為 O (N) 。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> intFreq;
        for (auto num:nums)
        {
            intFreq[num]++;
        }

        for (auto freq:intFreq)
        {
            save (freq, k);
        }

        vector<int> ans;
        for (int i=0; i<k; i++)
        {
            ans.push_back (result.top().first);
            result.pop();
        }
        return ans;
    }
private:
    struct heap_comp {
        bool operator() (const pair<int, int> p, const pair<int, int> q) {
            return p.second > q.second;
        }
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, heap_comp> result;
    void save (const pair<int, int>& input, int k)
    {
        result.push (input);
        if (result.size() > k )
        {
            result.pop ();
        }
    }
};

方法 2-2 MinHeap

這個方法跟 2-2 的差別在於利用 C++ STL greater<> ，不需要自己寫 Priority Queue 的 Compare function 。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> pq;
        unordered_map<int, int> record;
        for (auto num:nums) {
            record[num]++;
        }

        for (auto element:record) {
            pq.push({element.second, element.first});
            if(pq.size() > k) {
                pq.pop();
            }
        }
        vector<int> result;
        for (int i=0; i<k; i++) {
            result.push_back(pq.top().second);
            pq.pop();
        }
        return result;
    }
};

方法 3 Quick select

時間複雜度可達到 O (N) ，空間複雜度僅 O (1) 。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map <int, int> intFreq;
        for (auto num:nums)
        {
            intFreq[num]++;
        }
        vector<pair<int, int>> element;
        for (auto freq:intFreq)
        {
            element.push_back
            (make_pair (freq.first, freq.second));
        }
        int kth_smallest_index = element.size() 
                                - k - 1;

        quick_select (0, element.size()-1,
                    kth_smallest_index, element);
        vector<int> result;
        for (int i=0; i<k; i++)
        {
            result.push_back(element[element.size()-1-i].first);
        }
        return result;
    }
private:
    int quick_select (int left, int right, int kth,
                      vector<pair<int, int>>& intDict)
    {
        int pivot;
        while (right > left)
        {
            pivot = partition (left, right, intDict);
            if (pivot == kth)
                break;
            else if (pivot < kth)
            {
                left = pivot+1;
            }
            else
            {
                right = pivot-1;
            }
        }
        return pivot;
    }

    int partition (int left, int right,
                  vector<pair<int, int>>& intDict)
    {
        int shuffle = (rand()%(right-left+1)) + left;
        std::swap (intDict[shuffle], intDict[right]);
        int stored_index = left;
        for (int i=left; i<right; i++)
        {
            if (intDict[i].second <= intDict[right].second)
            {
                std::swap (intDict[i], intDict[stored_index]);
                stored_index++;
            }
        }
        std::swap (intDict[right], intDict[stored_index]);
        return stored_index;
    }
};

方法 4 Bucket sort

桶排序我就不描述，網路上可以找到很多資料

這個方法的時間複雜度可以到 O (n) ，空間複雜度也為 O(n) 。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> numFreq;
        int max_cnt = 0;
        for (auto num:nums)
        {
            max_cnt = max(max_cnt, ++numFreq[num]);
        }
        vector<vector<int>> bucket(max_cnt+1);
        for (auto num:numFreq)
        {
            bucket[num.second].push_back (num.first);
        }

        vector<int> result;
        for (int i=max_cnt; i>=0 && result.size()<k; i--)
        {
            for (auto num:bucket[i])
            {
                result.push_back (num);
                if (result.size() == k)
                    break;
            }
        }
        return result;
    }
};

延伸練習

Leetcode #703, #692, #215

總結

這類型題目可以使用 sorting, heap 或 quick select，透過練習以上經典的練習題，很快就可以熟悉這三種解法，反倒是要注意 C++ STL 的使用，如果不常使用的話，很容易忘記 STL 的用法，這類型的題目也可以拿來練習如何使用常見的 STL 用法。

Reference

Updated on 2022-12-29 07:57:42 星期四

作者: haogroot

CS:APP 學習筆記

共筆連結

CH2 Presentation and Maipulating Information

CH3 Machine-level Representation of Programs

CH7 Linking

參考資料

Linked List 的反轉操作 – 陪你刷題

Top K element – 陪你刷題

如何辨識 Top K element 類型題目

Leetcode #973 K Closest Points to Origin

方法 1 Sorting

方法 2-1 MinHeap

方法 2-2 MaxHeap

方法 3 Quick Select

Leetcode #347 Top K Frequent Elements

方法 1

方法 2-1 MinHeap

方法 2-2 MinHeap

方法 3 Quick select

方法 4 Bucket sort

延伸練習

總結

Reference