algo-aha

设第k小的数为x，表达式count(x){<=x的个数}是关于x的递增函数，条件式enough(x){count(x)>=k}满足二分搜索条件形式[0 0 ... 0 1 1 ...]。

同理，若找第k大的数，设第k大的数为x，表达式count(x){>=x的个数}是关于x的递减函数，条件式enough(x){count(x)<=k}满足二分搜索条件形式[0 0 ... 0 1 1 ...]。

复杂度：T(n)=T(n/2)+f(n)，f(n)是条件式的复杂度。根据主方法，看O(1)和O(f(n))哪个阶数高。若f(n)=O(n), T(n)=O(n)；若f(n)=O(1), T(n)=O(lgn)。

从行列有序的矩阵中找第k小的数，可用二分法猜结果，或者用最小堆从多个有序行中找。

乘法表中找第k小的数

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

int findKthNumber(int m, int n, int k) {
    // 猜第k小的数x，x在范围[1..m*n]
    int l = 0, u = m * n + 1;
    while (l + 1 < u) {
        int mid = l + (u - l) / 2;
        if (enough(mid, m, n, k)) {
            u = mid;
        } else {
            l = mid;
        }
    }
    return u;
}

bool enough(int x, int m, int n, int k) {
    // count(x){ <=x的个数 }是关于x的递增函数，
    // enough(x){ count(x)>=k }符合二分搜索的条件形式[0..0 1..1]
    int count = 0;
    for (int r = 1; r <= m; r++) {
        // 乘法表一行行看该行有多少乘积<=x
        count += min(x / r, n);
    }
    return count >= k;        
}

相似：https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix

bool enough(int value, vector<vector<int>>& matrix, int k) {
    int count = 0;
    for (auto &row : matrix) {
        // 看每行<=value的数有多少
        count += upper_bound(row.begin(), row.end(), value) - row.begin();
    }
    return count >= k;
}

数组两数间有距离，找第k小的距离

• https://leetcode.com/problems/find-k-th-smallest-pair-distance/

int smallestDistancePair(vector<int>& nums, int k) {
    // 两数的距离与数的位置无关，先排序数组
    sort(nums.begin(), nums.end());
    // 猜第k小的距离m，m的值范围[0, max(nums)-min(nums)]
    int l = 0, u = nums.back() - nums[0];
    while (l <= u) {
        int mid = l + (u - l) / 2;
        if (enough(mid, nums, k)) {
            u = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

bool enough(int m, vector<int> &nums, int k) {
    // count(m){ <=m的距离个数 }是关于m的递增函数，
    // enough(m){ count(m)>=k }满足二分搜索的条件形式[0..0 1..1]
    int count = 0;
    for (int j = 1; j < nums.size(); j++) {
        // 找 nums[j]-nums[i] <= m，nums[i] >= nums[j]-m
        int i = lower_bound(nums.begin(), nums.end(), nums[j] - m) - nums.begin();
        count += j - i; // 距离对：(i,j),(i+1,j),...,(j-1,j)
    }
    return count >= k;
}

第N小的A,B倍数

• https://leetcode.com/problems/nth-magical-number/
• https://leetcode.com/problems/ugly-number-iii/

int nthMagicalNumber(int N, int A, int B) {
    // 猜第N小的A,B倍数为x，x的取值范围为[min(A,B), N*min(A,B)]
    const int MOD = 1e9 + 7;
    int lcm = A / __gcd(A, B) * B;
    long l = min(A, B), u = (long)N * min(A, B);
    while (l <= u) {
        long mid = l + (u - l) / 2;
        if (enough(mid, A, B, lcm, N)) {
            u = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return l % MOD;
}

bool enough(long x, int A, int B, int lcm, int N) {
    // count(x){ <=x的A,B倍数的个数}是关于x的递增函数
    // enough(x){ count(x)>=N }满足二分搜索的条件形式[0..0 1..1]
    // 而 count(x) = x/A + x/B - x/lcm(A,B)
    return x / A + x / B - x / lcm >= N;
}