难度: 困难 | 标签: 二分查找

1. 题目描述

https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/
几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第k小的数字吗？
给定高度m 、宽度n 的一张 m * n的乘法表，以及正整数k，你需要返回表中第k 小的数字。

例 1：
输入: m = 3, n = 3, k = 5
输出: 3
解释:
1 2 3
2 4 6
3 6 9
第5小的数字是 3 (1, 2, 2, 3, 3).
例 2：
输入: m = 2, n = 3, k = 6
输出: 6
解释:
1 2 3
2 4 6
第6小的数字是 6 (1, 2, 2, 3, 4, 6).

注意：

  • m 和 n 的范围在 [1, 30000] 之间。
  • k 的范围在 [1, m * n] 之间。

通过次数: 13,828 | 提交次数: 24,877

2. 题解

2022-05-18 AC
我们无法把全部数字都求出来, 然后排序二分找到第k个
但是我们可以算 某一个数字前面有多少个小于它的数量, 那么就是二分枚举1 ~ n*m, 就找嘛
比如1 ~ 200, 我先看<=100的有多少个数字, 小于k个那就是值取小了, 那么我们就再看150, 大于k个就是取大了, 我们就看125
终归当l==r, 我们能找到那个恰好是小于k个数字的mid值, 他就是此时的l或r, 即要找的数

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/5/18 10:00
  6.  * Des: 668. 乘法表中第k小的数
  7.  *      https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table/
  8.  */
  10. class Solution
  11. {
  13.     /**
  14.      * @param Integer $m
  15.      * @param Integer $n
  16.      * @param Integer $k
  17.      * @return Integer
  18.      */
  19.     function findKthNumber($m, $n, $k)
  20.     {
  21.         $l = 1;
  22.         $r = $n * $m;
  23.         while ($l != $r) {
  24.             $mid = intval($r - ($r - $l) / 2);
  25.             $count = 0;
  26.             for ($i = 1; $i <= $m; $i++) {
  27.                 $count += min($n, intval($mid / $i));
  28.             }
  29.             if ($count < $k) {
  30.                 $l = $mid + 1;
  31.             } else {
  32.                 $r = $mid;
  33.             }
  34.         }
  35.         return $r;
  36.     }
  37. }
  39. var_dump((new Solution)->findKthNumber(3, 4, 5));
  40. var_dump((new Solution)->findKthNumber(2, 3, 6));
  42. /**
  43.  * 执行用时：164 ms, 在所有 PHP 提交中击败了100.00%的用户
  44.  * 内存消耗：18.7 MB, 在所有 PHP 提交中击败了100.00%的用户
  45.  * 通过测试用例：70 / 70
  46.  */