# Leetcode - Kth Smallest Number in Multiplication Table

violet posted @ May 05, 2020 08:07:12 AM in 算法 with tags BinarySearch Algorithm Golang , 219 阅读

https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/

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).
```

```func findKthNumber(m int, n int, k int) int {
low := 1
high := m * n + 1
var mid int
for low < high {
mid = low + (high - low)/2
c := count(mid, m, n)
if c >= k {
high = mid
} else {
low = mid + 1
}
}

return high
}

func count(mid, m, n int) int {
c := 0
for i := 1; i <= m; i++ {
tmp := min(mid/i, n)
c += tmp
}
return c
}

func min(a, b int) int {
if a < b {
return a
}
return b
}```

(输入验证码)
or Ctrl+Enter