ARTS 第9周 LeetCode 378 二分法 | 面向对象三要素你还记得吗？

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 等等这些。

欢迎关注我们的微信公众号，每天学习Go知识