题目

见 特定序列的第K小的数

算法分析

1. sort nlogn 4e6
2. C++ heap 每一行第一个放进去，小于$k$的时候怎么办？我们可以依次把队首取出来，然后把右边放进去 2e6
3. 桶排序，即对sort的优化 O(n) 1e6
4. quick-select O(n) 1e6
5. 二分答案 1-1000000 log(1000000)*500*log500 = 1.2e4

下面只给出最优解的代码：

C++代码

class Solution {
public:
    /**
     * @param arr: an array of integers
     * @param k: an integer
     * @return: the Kth smallest element in a specific array
     */
    int kthSmallest(vector<vector<int>> &arr, int k) {
        int l = 1, r = 1000000;
        while (l < r) {
            int mid = (l + r) >> 1;
            int cnt = 0;
            for (int i = 0; i < arr.size(); i++) {
                cnt += upper_bound(arr[i].begin(), arr[i].end(), mid) - arr[i].begin();
            }
            if (cnt < k) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};