668 Kth Smallest Number in Multiplication Table

Search…

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.Themandnwill be in the range [1, 30000].
2.Thekwill be in the range [1, m * n]
2. Implementation
(1) Binary Search
思路: Kth Smallest Element in a Sorted Matrix 一样的解法
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个(列数)个数

659 Split Array into Consecutive Subsequences

692 Top K Frequent Words

Last modified 2yr ago

Copy link

Contents

668. Kth Smallest Number in Multiplication Table

1. Question

2. Implementation

3. Time & Space Complexity

668. Kth Smallest Number in Multiplication Table​

1. Question

2. Implementation

3. Time & Space Complexity

668. Kth Smallest Number in Multiplication Table