Force deduction solution summary 668- the smallest number k in the multiplication table

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Almost everyone uses   Multiplication table . But you can quickly find the number... In the multiplication table k Small number ？

Given height m 、 Width n One of the  m * n The multiplication table of , And positive integers k, You need to go back to... In the table k  Small numbers .

example  1：

Input : m = 3, n = 3, k = 5
Output : 3
explain : 
Multiplication table :
1    2    3
2    4    6
3    6    9

The first 5 The small number is 3 (1, 2, 2, 3, 3).
example 2：

Input : m = 2, n = 3, k = 6
Output : 6
explain : 
Multiplication table :
1    2    3
2    4    6

The first 6 The small number is 6 (1, 2, 2, 3, 4, 6).
Be careful ：

m and  n  The scope of [1, 30000] Between .
k The scope of [1, m * n] Between .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/kth-smallest-number-in-multiplication-table
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  I didn't come up with an answer to the question , Finally, I figured it out by looking at the solution of the problem .
*  I still have a doubt , Each dichotomy search is better than middle How many times are there small numbers , How to guarantee the last one middle+1 perhaps right It must be the number in the multiplication table ？

Code ：

public class Solution668 {

    public int findKthNumber(int m, int n, int k) {
        int left = 1;
        int right = m * n;
        int middle = 0;
        while (left < right) {
            middle = left + (right - left) / 2;
            // Seek less than middle The number of 
            int count = 0;
            for (int i = 1; i <= m; i++) {
                int min = Math.min(m, middle / i);
                count += min;
            }
            if (count >= k) {
                right = middle;
                continue;
            }
            left = middle + 1;
        }
        return left;
    }
}