Problem
Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?
Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.
Example 1:
Input: m = 3, n = 3, k = 5 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 3 6 9 The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Example 2:
Input: m = 2, n = 3, k = 6 Output: Explanation: The Multiplication Table: 1 2 3 2 4 6 The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).
Note:
- The
mandnwill be in the range [1, 30000]. - The
kwill be in the range [1, m * n]
Solution 1: Nth element (MLE)
Time complexity: O(mn)
Space complexity: O(mn)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// 59 / 69 test cases passed. class Solution { public: int findKthNumber(int m, int n, int k) { vector<int> s(m * n); auto it = begin(s); for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) *it++ = i * j; nth_element(begin(s), begin(s) + k - 1, end(s)); return s[k - 1]; } }; |
Solution2 : Binary Search
Find first x such that there are k elements less or equal to x in the table.
Time complexity: O(m*log(m*n))
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua, 12 ms class Solution { public: int findKthNumber(int m, int n, int k) { int l = 1; int r = m * n + 1; while (l < r) { int x = l + (r - l) / 2; if (LEX(m, n, x) >= k) r = x; else l = x + 1; } return l; } private: // Returns # of elements in the m*n table that are <= x int LEX(int m, int n, int x) { int count = 0; for (int i = 1; i <= m; ++i) count += min(n, x / i); return count; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 16 ms class Solution { public int findKthNumber(int m, int n, int k) { int l = 1; int r = m * n + 1; while (l < r) { int x = l + (r - l) / 2; if (LEX(m, n, x) >= k) r = x; else l = x + 1; } return l; } // Returns # of elements in the m*n table that are <= x private int LEX(int m, int n, int x) { int count = 0; for (int i = 1; i <= m; ++i) count += Math.min(n, x / i); return count; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# Author: Huahua, 976 ms class Solution: def findKthNumber(self, m, n, k): def LEX(m, n, x, k): count = 0 for i in range(1, min(m + 1, x + 1)): count += min(n, x // i) if count >= k: return count return count l = 1 r = m * n + 1 while l < r: x = l + (r - l) // 2 if LEX(m, n, x, k) >= k: r = x else: l = x + 1 return l |
Related Problems
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment