LeetCode 668. 乘法表中第k小的数

Categories:

题目描述
思路分析
1. 解法一：二分查找（推荐）
相似题目

题目描述

✅ 668. 乘法表中第k小的数

思路分析

解法一：二分查找（推荐）

核心思路：

二分答案 mid，统计乘法表中 ≤ mid 的数有多少。

每行贡献 min(n, mid / i)。

计数 ≥ k 时缩小右边界，否则扩大左边界。

复杂度分析：

时间复杂度：O(m log(m*n))，其中 m 表示行数。

空间复杂度：O(1)。

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

func findKthNumber(m int, n int, k int) int {
	left, right := 1, m*n
	for left < right {
		mid := left + (right-left)/2
		count := 0
		for i := 1; i <= m; i++ {
			if mid/i < n {
				count += mid / i
			} else {
				count += n
			}
		}
		if count >= k {
			right = mid
		} else {
			left = mid + 1
		}
	}

	return left
}

相似题目

题目	难度	考察点
378. 有序矩阵中第 K 小的元素	中等	二分
719. 找出第 K 小的数对距离	困难	二分
786. 第 K 个最小的素数分数	中等	二分
1539. 第 k 个缺失的正整数	简单	二分
215. 数组中的第K个最大元素	中等	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/46067009