ARTS

ARTS 是陳浩（網名左耳朵耗子）在極客時間專欄裏發起的一個活動，目的是通過分享的方式來堅持學習。

每人每週寫一個 ARTS：Algorithm 是一道算法題，Review 是讀一篇英文文章，Technique/Tips 是分享一個小技術，Share 是分享一個觀點。

本週內容

本週你將看到：

1. 二分查找類型題能還難到什麼程度？
2. 本週沒有文章推薦；
3. 本週也沒有技巧可講；
4. 你真的在踐行面向對象編程麼？

Algorithm

本週的算法題是兩道比較「高級」的二分查找題目：

LeetCode 378 Kth Smallest Element in a Sorted Matrix

LeetCode 719 Find K-th Smallest Pair Distance

其實二分查找這種題，在面試中經常扮演的角色是「一問就會，一寫就錯」。雖然算法的思想非常簡單，但是要寫出正確的代碼還是有一些需要注意的地方，尤其是對於迭代過程中新的 mid 如何取值的問題。

我們先來看第一道題，求排序矩陣掙的第 K 小元素。當然，這題完全可以直接遍歷矩陣然後給矩陣整體排序，最後直接返回排序數組的第 K 個數字。只不過這樣的話就沒用題目中給的兩個條件：首先，矩陣中的行是從小到大排序的；其次，矩陣中的列也是從小到大排序的。這樣排序的矩陣等效於從左上角到右下角大致是有序的。即，從左上角到右下角大致遞增。

注意題目要求的是求第 K 小的數字，我們可以猜想某個數字(guess)就是要求的第 K 小數字，然後去矩陣中找不大於該數字的數字個數，這裏記爲 count. 如果 count >= k 那麼就嘗試讓 guess 縮小，直到找到某個 guess 的值是最小的滿足 count == k 的值。這時的 guess 就是我們要找的「第 K 小元素」。如果你做過「在排序數組中查找符合某種條件的下標」這類題目，那麼你一定會覺得上面的過程非常熟悉，這就是二分查找的典型場景，只不過邊界的判斷依據變得複雜了一些。

下面是參考代碼，最終利用到矩陣的特性之後時間複雜度下降到了 O(N*logN) 級別。

func kthSmallest(matrix [][]int, k int) int {
    d := len(matrix)
    mid, lo, hi := 0, matrix[0][0], matrix[d-1][d-1]
    for lo <= hi {
        mid = (lo + hi) / 2
        curr := check(matrix, mid)
        // 下面兩個條件其實可以合併成 curr <= k
        // 爲了便於理解還是保持最原始的狀態
        if curr == k {
            if check(matrix, mid-1) < k {
                return mid
            }
            // if check(matrix, mid-1) == k
            hi = mid - 1
        } else if curr > k {
            if check(matrix, mid-1) < k {
                return mid
            }
            hi = mid - 1
        } else if curr < k {
            lo = mid + 1
        }
    }
    return mid
}

func check(matrix [][]int, target int) int {
    d := len(matrix)
    count, i, j := 0, d-1, 0
    // i = 0 只有在開始的時候，i<0 只有左下角都比 target 小纔可能出現
    for i >= 0 && j < d {
        // matrix[i][j] <= target 說明第 i 行第 j 列全都小於等於 target
        // count 增加列長：i+1
        if matrix[i][j] <= target {
            count += i + 1
            j++
        } else {
            // matrix[i][j] > target 說明本行全部大於 target
            // 向上移動一行 i-- 再比較
            i--
        }
    }
    return count
}

接着來看第二道題，求數組中第 K 小的「數字距離」。因爲兩道題目實在是太類似了，具體思維過程不再贅述。唯一需要注意的就是，題中的「距離」不包含每個數字和自己的「距離」。也就是尋找兩個數字的差的過程中，兩個指針需要指向不同的數字。下面上代碼。

// 這道題和 378.kth-smallest-element-in-a-sorted-matrix 非常類似
// 只是在求 mid 滿足要求的數量時稍微有點區別
// 看來二分查找類型的題難度提升只能在邊界判斷的位置做文章了
func smallestDistancePair(nums []int, k int) int {
    // 先給 nums 排序，測試例要求 nums 長度最少是 2, 不用做長度判斷
    sort.Slice(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })
    mid, lo, hi := 0, 0, nums[len(nums)-1]-nums[0]
    for lo <= hi {
        mid = (lo + hi) / 2
        c := shorterCount(nums, mid)
        if c >= k {
            if shorterCount(nums, mid-1) < k {
                return mid
            }
            hi = mid - 1
        } else {
            lo = mid + 1
        }
    }
    return mid
}

// 返回差值小於等於 guess 的數對的數量
// @guess 猜測的滿足要求的數字
// 可以 AC 但是效率不高畢竟 O(n^2)
// func shorterCount(nums []int, guess int) int {
//     var count int
//     for i := 0; i < len(nums)-1; i++ {
//         for j := i+1; j < len(nums); j++ {
//             if nums[j]-nums[i] <= guess {
//                 count++
//             }
//         }
//     }
//     return count
// }

// 返回差值小於等於 guess 的數對的數量
// @guess 猜測的滿足要求的數字
// 複雜度應該介於 O(n) 和 O(n^2) 之間，但判題系統給出的時間提升很多 10% -> 90%
func shorterCount(nums []int, guess int) int {
    left, count := 0, 0
    for right := 1; right < len(nums); right++ {
        for left < len(nums) && nums[right] - nums[left] > guess {
            left += 1
        }
        count += right - left
    }
    return count
}

Review 文章推薦

本週因爲實在太忙(lan)，沒有直的推薦的問題件。哭哭。

Tip 編程技巧

本週因爲實在太忙(lan)，沒有收集到任何一個小技巧。又哭哭。

Share 靈光一閃

你能準確回答「面向對象的三個特徵」是什麼，以及用簡短的代碼給出一個例子嗎？

我想對於剛工作時間不長的新人碼農來說，這個問題不難回答。大家早已將「封裝」「繼承」「多態」背的滾瓜爛熟，將之前默寫過幾遍的著名「動物園」例子瀟灑的寫出來以證明自己深諳面向對象之禪。但是對於很多工作了幾年，甚至五年以上的老(cai)鳥來說，不是每個人都能把上面的三點時常放在心上。

一切都要從這週五的一個功能開發說起，簡單來說就是增加一個小小的數據備份任務。然後因爲數據有若干種，每種數據需要使用不同的 struct 以及相對應的 DB 讀寫操作。這其實就是每個老鳥在菜鳥時期滾瓜爛熟的動物園模型的變型，至少可以用多態的方式減少絕大部分的重複代碼。但我在項目裏看到了從前年到今年，包括三四位同時在增加針對不同類型的數據備份時寫的「重複代碼」。這些重複代碼如果 diff 一下的話，可能只有 logger 的參數和寫入 DB 的表名不同而已，而我卻看到那個目錄裏有這樣幾乎完全重複的十來個文件。這些文件完全可以被一個抽象的 interface 和以多態的方式使用上面 interface 的不同實現的兩個文件取代，但是這些「自己複製自己」的代碼就這樣驕傲的羅列在項目裏。

可能業務代碼寫太多連基本的抽象能力都喪失了，一個簡單的「接口+實現」的抽象就能節省至少十個文件的代碼量的事情，居然沒有一個人想到。但是也可能事實是讓代碼看起來「多」會增加隱形 KPI.

本週閱讀列表

• 極客時間 MySQL 專欄
  索引 上
  索引 下
  全局鎖
  行鎖
• reviewdog 曹春暉
  Golang 代碼檢查工具，可以幫助提升項目質量，能檢查出未處理的 error 以及
• 一個案例徹底弄懂如何正確使用 mysql inndb 聯合索引
  文章確實對聯合索引的某些情況解釋的很好，但是並不能「一文讀懂」。文中的聯合索引示例圖確實很詳細。看完之後還是有個疑問：爲什麼聯合索引第一個字段作爲範圍條件時，聯合索引中的第二個字段不能應用到索引中去（確實 explain 中可以看到 key_len = 4），而交換 status 和 audit 在聯合索引中的順序之後就可以應用到第二個索引字段？
• A whirlwind tour of Go’s runtime environment variables
  介紹 Go 的一些運行時相關的參數，比如 GOTRACEBACK GOMAXPROCS gctrace schedtrace 等等這些。