【每日算法Day 83】鄰居小孩一年級就會的乘法表，你會嗎？
- 2020 年 4 月 2 日
- 筆記
題目鏈接
LeetCode 668. 乘法表中第k小的數[1]
題目描述
幾乎每一個人都用乘法表。但是你能在乘法表中快速找到第 小的數字嗎？
給定高度 、寬度 的一張 的乘法表，以及正整數 ，你需要返回表中第 小的數字。
示例1
輸入： m = 3, n = 3, k = 5 輸出： 3 解釋： 乘法表: 1 2 3 2 4 6 3 6 9 第5小的數字是 3 (1, 2, 2, 3, 3).
示例2
輸入： m = 2, n = 3, k = 6 輸出： 6 解釋： 乘法表: 1 2 3 2 4 6 第6小的數字是 6 (1, 2, 2, 3, 4, 6).
說明：
- 和 的範圍在 之間。
- 的範圍在 之間。
題解
二分法
因為 數量級是 級別的，所以顯然不能直接枚舉，要想一個對數級別的算法。
對數級別首先想到的肯定是二分了，我們二分第 小的數 ，然後求出乘法表中小於等於 的數的數量 。如果發現 ，那就說明這個答案太大了，還可以繼續縮小。否則的話答案太小了，得增大一點。
那麼對於枚舉的答案 來說，如何找到乘法表中有多少小於等於它的數呢？我們可以直接從 開始枚舉，和 相乘並且結果小於等於 的數有 個，當然還有個 的限制，所以是 個。然後和 相乘並且結果小於等於 的數有 個。依此類推下去，最終和 相乘並且結果小於等於 的數有 個。
所以最終小於等於 的個數 就可以計算為：
二分法+優化
當然這題計算還可以進行一些優化。
首先第 小的數是一定小於等於 的，所以我們的二分上界可以定為 。
其次注意到當 之後，個數一定是 ，所以 只需要枚舉到 就行了。
然後當 時，有 ，所以這部分的求和結果就是 。所以 又可以寫為：
最後，對於某個 ，我們會發現如果 慢慢增大，某一段連續區間內 的值都是不會變的。而 最大可以增大到 ，那麼這一段區間內的求和就可以直接算出來：
接着令 直接跳轉到 就可以了，這樣就不用慢慢加 計算了。要特別注意的是最後不能超過 。
理論上這樣的計算複雜度是更低的，但是實際運行中速度還不如不加最後一步優化，可能原因是除法操作次數太多了，反而總的操作次數超過了直接遍歷計算。
代碼
二分法（c++）
class Solution { public: int findKthNumber(int m, int n, int k) { int l = 1, r = m*n; while (l < r) { int mid = l+((r-l)>>1); if (enough(mid, m, n, k)) r = mid; else l = mid+1; } return l; } bool enough(int x, int m, int n, int k) { int cnt = 0; for (int i = 1; i <= m; ++i) { cnt += x/i<n?x/i:n; } return cnt >= k; } };
二分法+優化（c++）
class Solution { public: int findKthNumber(int m, int n, int k) { int l = 1, r = k; while (l < r) { int mid = l+((r-l)>>1); if (enough(mid, m<mid?m:mid, n<mid?n:mid, k)) r = mid; else l = mid+1; } return l; } bool enough(int x, int m, int n, int k) { int cnt = n*(x/n), d = 0; for (int i = (x/n)+1; i <= m; i = d+1) { d = x/(x/i); cnt += (x/i)*((d<m?d:m)-i+1); } return cnt >= k; } };
二分法（python）
class Solution: def findKthNumber(self, m: int, n: int, k: int) -> int: def enough(x, m, n, k): cnt = 0 for i in range(1, m+1): cnt += x//i if x//i<n else n return cnt >= k l, r = 1, m*n while l < r: mid = l+((r-l)>>1) if enough(mid, m, n, k): r = mid else: l = mid+1 return l
二分法+優化（python）
class Solution: def findKthNumber(self, m: int, n: int, k: int) -> int: def enough(x, m, n, k): cnt, i, d = n*(x//n), x//n+1, 0 while i <= m: d = x//(x//i) cnt += (x//i)*((d if d<m else m)-i+1) i = d+1 return cnt >= k l, r = 1, k while l < r: mid = l+((r-l)>>1) if enough(mid, m if m<mid else mid, n if n<mid else mid, k): r = mid else: l = mid+1 return l
參考資料
[1]
LeetCode 668. 乘法表中第k小的數: https://leetcode-cn.com/problems/kth-smallest-number-in-multiplication-table/
作者簡介：godweiyang，知乎同名，華東師範大學計算機系碩士在讀，方向自然語言處理與深度學習。喜歡與人分享技術與知識，期待與你的進一步交流~
