668 Kth Smallest Number in Multiplication Table

1. Question

Nearly every one have used the Multiplication Table. But could you find out thek-thsmallest number quickly from the multiplication table?
Given the heightmand the lengthnof am * nMultiplication Table, and a positive integerk, you need to return thek-thsmallest number in this table.
Example 1:
1
Input: m = 3, n = 3, k = 5
2
3
Output:
4
Explanation:
5
6
The Multiplication Table:
7
1 2 3
8
2 4 6
9
3 6 9
10
11
The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Copied!
Example 2:
1
Input: m = 2, n = 3, k = 6
2
3
Output:
4
Explanation:
5
6
The Multiplication Table:
7
1 2 3
8
2 4 6
9
10
The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).
Copied!
Note:
  1. 1.
    Themandnwill be in the range [1, 30000].
  2. 2.
    Thekwill be in the range [1, m * n]

2. Implementation

(1) Binary Search
1
class Solution {
2
public int findKthNumber(int m, int n, int k) {
3
int start = 1, end = m * n, mid = 0;
4
5
while (start < end) {
6
mid = start + (end - start) / 2;
7
8
int count = searchAndCount(mid, m, n);
9
10
if (count < k) {
11
start = mid + 1;
12
}
13
else {
14
end = mid;
15
}
16
}
17
return start;
18
}
19
20
public int searchAndCount(int target, int m, int n) {
21
int row = m, col = 1, count = 0;
22
23
while (row >= 1 && col <= n) {
24
if (row * col <= target) {
25
count += row;
26
++col;
27
}
28
else {
29
--row;
30
}
31
}
32
return count;
33
}
34
}
Copied!
(2) Heap
1
class Solution {
2
public int findKthNumber(int m, int n, int k) {
3
PriorityQueue<CellInfo> minHeap = new PriorityQueue<>();
4
5
for (int i = 1; i <= n; i++) {
6
minHeap.add(new CellInfo(1, i, i));
7
}
8
9
for (int i = 2; i <= k; i++) {
10
CellInfo curCell = minHeap.remove();
11
// System.out.println("current value: " + curCell.val);
12
int curRow = curCell.row;
13
int curCol = curCell.col;
14
15
if (curRow + 1 <= m) {
16
minHeap.add(new CellInfo(curRow + 1, curCol, (curRow + 1) * curCol));
17
}
18
}
19
return minHeap.peek().val;
20
}
21
22
class CellInfo implements Comparable<CellInfo> {
23
int row, col, val;
24
25
public CellInfo(int row, int col, int val) {
26
this.row = row;
27
this.col = col;
28
this.val = val;
29
}
30
31
public int compareTo(CellInfo that) {
32
return this.val - that.val;
33
}
34
}
35
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O((m+n)log(mn)), 空间复杂度O(1)
Heap: 时间复杂度O(m * n * logn), 空间复杂度O(logn), heap存储最多n个(列数)个数