algo-aha

无序数组中第k小的数

把快排划分找第k大的数的partition函数改成小的往前抛，二分搜索函数相同。

int findKthSmallest(vector<int>& nums, int k) {
    int l = 0, u = (int)nums.size() - 1;
    k--; // k是1-based，变成下标作比较
    while (l <= u) {
        int p = partition(nums, l, u);
        if (k == p) break;
        if (k < p) u = p - 1;
        else l = p + 1;
    }
    return nums[k];
}

多个有序数组中第k小的数

设x是第k小的数，二分搜索条件enough(x)表示"<=x的个数"count>=k。当猜的x不断变大时，二分搜索输出[0 0 ... 0 1 1 ...]。

若是找第k大的数：设x是第k大的数，二分搜索条件enough(x)表示">=x的个数"count<=k。

两个有序数组中找第k小的数

上题的特例。或者另种方式的二分搜索，见中位数

用k元堆找第k小的数

无序数组中找第k小用最大堆。数据流不断插入并弹出，保持k元堆，弹出N-k次。

作为对比，多个有序数组中找第k小用最小堆，只插入各行最小的数，弹出k-1次。

动态有序集中第k小的节点

扩展红黑树（bst），节点要记录以当前节点为根的子树大小，这就相当于做好了数组中的划分操作。