Algorithm: 每周至少做一個(gè) LeetCode 的算法題
劍指 Offer 12. 矩陣中的路徑

兩個(gè)關(guān)鍵: 1起始位置 2行動(dòng)方向
一般都使用深度優(yōu)先或者廣度優(yōu)先算法遍歷(遞歸法)
回溯法三個(gè)步驟

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }

    for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大?。? {
        處理節(jié)點(diǎn);
        backtracking(路徑，選擇列表); // 遞歸
        回溯，撤銷處理結(jié)果
    }
}

LeetCode 378 有序矩陣中第 K 大的數(shù)
解法1: 使用堆排序

int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<int> q;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                q.emplace(matrix[i][j]);
                if (q.size() > k) q.pop();
            }
        }
        return q.top();
}

解法2: 使用二分法 -> 對(duì)值進(jìn)行二分搜索, 不是索引二分搜索
二分查找法有兩種: 基于索引和基于數(shù)值的()
1 基于索引即根據(jù)數(shù)組中元素下標(biāo)
2 基于數(shù)值即根據(jù)數(shù)組的首尾元素找到中間值, 確定大于等于或小于等于中間值的數(shù)組元素.

拓展1: 240. 搜索二維矩陣 II
拓展2: 使用BFPRT 法實(shí)現(xiàn) O(n)查找第k 小的數(shù)
1 找數(shù)組中第 k 小的數(shù): 1 快排, 2 數(shù)組中的 nums[k-1], 時(shí)間復(fù)雜度: O(nlgn)
2 BFPRT 算法每次選擇五分中位數(shù)作為 pivot, 為了是劃分合理, 避免最壞情況發(fā)生.
算法步驟:
(1）將輸入數(shù)組的n個(gè)元素劃分為n/5組，每組5個(gè)元素，且至多只有一個(gè)組由剩下的n%5個(gè)元素組成。
（2）尋找n/5個(gè)組中每一個(gè)組的中位數(shù)，首先對(duì)每組的元素進(jìn)行插入排序，然后從排序過的序列中選出中位數(shù)。
（3）對(duì)于（2）中找出的n/5個(gè)中位數(shù)，遞歸進(jìn)行步驟（1）和（2），直到只剩下一個(gè)數(shù)即為這n/5個(gè)元素的中位數(shù)，找到中位數(shù)后并找到對(duì)應(yīng)的下標(biāo)p。
（4）進(jìn)行Partion劃分過程，Partion劃分中的pivot元素下標(biāo)為p。
（5）進(jìn)行高低區(qū)判斷即可。
本算法的最壞時(shí)間復(fù)雜度為O(n)，值得注意的是通過BFPTR算法將數(shù)組按第K?。ù螅┑脑貏澐譃閮刹糠郑@高低兩部分不一定是有序的，通常我們也不需要求出順序，而只需要求出前K大的或者前K小的。

Review: 閱讀并點(diǎn)評(píng)至少一篇英文技術(shù)文章
(1)Developing Web Applications with Flask
(2)Building a Flask Web Application (Flask Part 2)
(3)9 Ways to Boost Your Swift Code Performance

Tips: 學(xué)習(xí)至少一個(gè)技術(shù)技巧
Flask 實(shí)現(xiàn)的 web app 中的 MVC 模式.

Share: 分享一篇有觀點(diǎn)和思考的技術(shù)文章
百度 iOS 客戶端 Objective-C Swift 組件化混編之路(1)