668. Kth Smallest Number in Multiplication Table

Link

Solution

看到這題要怎麼想到binary search?

binary search是用來尋找在某個範圍中滿足條件的最小元素

所以可以透過這個概念去找出一個最小元素使得之滿足:

1. 所有比它小的multiplication count會 >=K

  public int findKthNumber(int m, int n, int k) {
        int min = 1, max = m*n;
        while(max > min){
            int mid = min + (max-min)/2;
            if(enough(m, n, mid, k)){
                max = mid;
            }else{
                min = mid+1;
            }
        }
        return min;
    }
    
    public boolean enough(int m, int n, int num, int k){
        int count = 0;
        for(int i = 1; i <= m; i++){
            int add = num/i;
            if(add != 0){
                count += Math.min(n, add);
            }
            else{
                break;
            }
        }
        return count >= k;
    }