leetcode 668. Kth Smallest Number in Multiplication Table 有序矩阵搜索 + 右上角二分搜索

心已赠人 2022-06-03 07:42 86阅读 0赞

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 m and n will be in the range \[1, 30000\].  
The k will be in the range \[1, m \* n\]

本题题意就是在一个m\*n的乘法表，然后要求找到第k小的数字

建议和[leetcode 240. Search a 2D Matrix II 矩阵搜索 + 右上角搜索][leetcode 240. Search a 2D Matrix II _ _] 和 [leetcode 378. Kth Smallest Element in a Sorted Matrix][]一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    #include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int findKthNumber(int m, int n, int k)
        {
            int left = 1, right = m*n;
            while (left < right)
            {
                int mid = (right - left) / 2 + left;
                int count = calaCount(m, n, mid);
                if (count < k)
                    left = mid + 1;
                else
                    right = mid;
            }
            return left;
        }
    
        int calaCount(int row, int col, int target)
        {
            int res = 0;
            int i = 1, j = col;
            while (i <= row && j >= 1)
            {
                if (i*j <= target)
                {
                    res += j;
                    i++;
                }
                else
                    j--;
            }
            return res;
        }
    };

[leetcode 240. Search a 2D Matrix II _ _]: http://blog.csdn.net/jackzhang_123/article/details/78091820
[leetcode 378. Kth Smallest Element in a Sorted Matrix]: http://blog.csdn.net/jackzhang_123/article/details/78174215