企业官网建设流程全解析

Approach: Binary Search on the Answer Value

You can’t jump straight to the k-th smallest value, but given a candidate
“x”, you can count in O(m) how many entries are ≤ x. Row
“i” holds
“i, 2i, 3i, …, n·i”, so the entries ≤ x in that row number
“min(n, x / i)”. Sum over all rows.

“count(x)” is monotonically non-decreasing, so binary search for the smallest x with count(x) ≥ k — that’s exactly the k-th smallest entry.

class Solution {
fun findKthNumber(m: Int, n: Int, k: Int): Int {
var a = m
var b = n
if (a > b) { val t = a; a = b; b = t } // a = min(m, n)

// Number of entries in the multiplication table that are <= x. fun countLe(x: Int): Int { var cnt = 0 for (i in 1..a) { cnt += minOf(b, x / i) if (cnt >= k) return cnt // early exit: only need cnt >= k } return cnt } var lo = 1 var hi = a * b // answer always lies in [1, m*n] while (lo < hi) { // standard lower_bound val mid = lo + (hi - lo) / 2 if (countLe(mid) >= k) hi = mid else lo = mid + 1 } return lo // lo == hi == k-th smallest }

}

Key details

• Swap
  “m”/
  “n” so the counting loop runs only
  “min(m, n)” times.

“Int” is sufficient:
“m * n ≤ 3·10⁴ · 3·10⁴ = 9·10⁸”, comfortably inside
“Int.MAX_VALUE” (2.1·10⁹). If you prefer extra headroom, switch
“cnt”,
“lo”,
“hi”,
“mid” to
“Long” and cast on return.

“countLe” is a local function, so
“return cnt” exits only that helper — a
“break” inside a counting lambda would need a label.

• Early
  “return” once
  “cnt >= k”: the helper is only compared against
  “k”, so an exact count beyond
  “k” is wasted work.

“lo + (hi - lo) / 2” avoids overflow by habit, and
“while lo < hi” +
“hi = mid” is the lower-bound template — on exit
“lo” is the answer directly.

Complexity

• Time: O(m · log(m·n)), with m = min(m, n)
• Space: O(1)

The counting logic is identical to the Python version I cross-checked against brute force for all
“m, n ≤ 12” and every valid
“k” (zero mismatches), and it reproduces the official cases:
“(3,3,5) → 3”,
“(2,3,6) → 6”,
“(42,34,401) → 126”.