LeetCode: 668. Kth Smallest Number in Multiplication Table

发表于 | 分类于

题目描述

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:

1
2
3
4
5
6
7
8
9
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:

1
2
3
4
5
6
7
8
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).

真的是挺难的一道二分查找题，主要也是想不到可以这么做。

令left = 1,right=m*n得到mid然后去计算multiplication table中小于mid的个数cnt。如果小于，则令right=mid否则则left=mid+1，最后返回left。

这里可以不用考虑left是否在table中，因为这样做的话是肯定在table里的。因为left一定能找到一个在table中的数字，满足在table中的条件，如果找到了，那么left就不会有变化了，接下来都是right在进行收敛。另外，这里不能用right=mid-1，是因为mid得到的cnt是一个大于等于实际k的值(比如第一个例子，mid为6的时候，cnt为8，如果在k=7点时候直接right=mid-1的话，会永远找不到值)，所以right=mid，而在left=mid+1则没有问题。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int left = 1;
        int right = n*m;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            int cnt = 0;
            for (int i = 1; i <= m; i++) {
                cnt += min(mid/i, n);
            }
            if (cnt < k) {
                left = mid+1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};