Hard

题目描述

几乎每个人都使用过乘法表。大小为 m x n 的乘法表是一个整数矩阵 mat，其中 mat[i][j] == i * j（1-indexed）。

给你三个整数 m、n 和 k，请你返回大小为 m × n 的乘法表中第 k 小的数。

示例 1：

输入：m = 3, n = 3, k = 5
输出：3
解释：第 5 小的数字是 3。

示例 2：

输入：m = 2, n = 3, k = 6
输出：6
解释：第 6 小的数字是 6。

提示：

  • 1 <= m, n <= 3 * 10^4
  • 1 <= k <= m * n

解题思路

解题思路

这道题要求在 m×n 的乘法表中找到第 k 小的元素。如果直接生成整个乘法表然后排序，会消耗大量内存和时间。

关键观察：

  1. 乘法表中最小值是 1，最大值是 m×n
  2. 对于任意值 x，我们可以快速计算出乘法表中小于等于 x 的元素个数
  3. 在第 i 行中，小于等于 x 的元素个数为 min(n, x/i)

二分查找解法： 我们可以对答案进行二分查找。对于候选答案 mid，计算乘法表中小于等于 mid 的元素个数：

  • 如果个数 >= k，说明第 k 小的数 <= mid，在左半部分继续查找
  • 如果个数 < k，说明第 k 小的数 > mid，在右半部分继续查找

计算小于等于 x 的元素个数： 遍历每一行 i（1到m），在第 i 行中，小于等于 x 的元素个数为 min(n, x/i)。

时间复杂度为 O(m * log(m*n))，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = countLessEqual(m, n, mid);
            
            if (count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
private:
    int countLessEqual(int m, int n, int target) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            count += min(n, target / i);
        }
        return count;
    }
};

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def count_less_equal(target):
            count = 0
            for i in range(1, m + 1):
                count += min(n, target // i)
            return count
        
        left, right = 1, m * n
        
        while left < right:
            mid = left + (right - left) // 2
            if count_less_equal(mid) >= k:
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    public int FindKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = CountLessEqual(m, n, mid);
            
            if (count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
    
    private int CountLessEqual(int m, int n, int target) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            count += Math.Min(n, target / i);
        }
        return count;
    }
}

var findKthNumber = function(m, n, k) {
    const countLessEqual = (target) => {
        let count = 0;
        for (let i = 1; i <= m; i++) {
            count += Math.min(n, Math.floor(target / i));
        }
        return count;
    };
    
    let left = 1, right = m * n;
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        if (countLessEqual(mid) >= k) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m * log(m*n))二分查找进行 log(m*n) 次，每次计算需要 O(m)
空间复杂度O(1)只使用常数级额外空间

相关题目