找到n中最小的k个数

题目：n个数中，求最小的前k个数。

这道题在各个地方都看到过，在国内出现的频率也非常高。

面完阿里回来听说这道题又被考了，所以还是决定回来写一写，对于这种高频题。。。顺便再吐槽一下阿里的面试，我竟然一道题都不用做，只是纯粹地过简历。。。导致我都不知道我究竟错在哪里。

解法：

1. brute force。 O(k*n)复杂度；

2. sort。O(k+n*lgn)复杂度；

3. 最大堆。每次替代的是大小为k的最大堆的最大值。O(k+(n-k)lgk)复杂度。

int findKthByHeap(int arr[], int n, int k) {
    make_heap(arr, arr + k);

    for (int i = k; i < n; ++i) {
        if (arr[i] < arr[0]) {
            pop_heap(arr, arr + k); // pop_heap()用于弹出堆中的第一个元素，并把它放到区间的最后一个位置，然后重新将前面的元素构建成一个堆。
            arr[k - 1] = arr[i];  //替换最后一个数
            push_heap(arr, arr + k); //pop_heap()用于将指定区间的最后一个元素加入堆中并使整个区间成为一个新的堆。注意前提是最后一个元素除外的所有元素已经构成一个堆。
        }
    }

    return arr[0];
}

4. 最小堆。和sort类似，只是建堆后只求前k次。O(n+k*lgn)复杂度。在网上看到一个优化，就是pop出第k小的数（堆顶）的时候，最多只需要调整k-1层（不需要调到堆底）。所以可以优化到O(n+k^2)。当然这个建堆需要O(n)的空间复杂度，所以还是弱一点。

int findKthByHeap(int arr[], int n, int k) {
    make_heap(arr, arr + n, greater<int>());    
    for (int i = 0; i < k - 1; ++i) {
        pop_heap(arr, arr + n, greater<int>());
        n--;
    }
    return arr[0];
}

5. 类quick sort。求第k小的数。pivot用的是“五分化中项的中项”。因为每次划分之后，只需要考虑其中一部分的数，证明过程类似于堆排序建堆用了O(n)的开销证明。开销也在O(n)。

关于partition，要用的是双向划分， 避免的是所有数字都相等的情况。

双向划分也有两种方式，最后一种最为简洁，关键在于arr[l]这个元素因为先保存下来了，所以替换它是安全的，所以我们是先找arr[r]，然后将它保存到arr[l]；然后再找arr[l]，将它保存到arr[r]。循环退出时，arr[l]已经保存到arr[r]的位置了，所以循环不变式是arr[l]仍然可以安全地被替代。

int partition2(int arr[], int n) {
    int l = 0;
    for (int i = 1; i < n; ++i) {
        if (arr[i] < arr[0]) {
            swap(arr[++l], arr[i]);
        }
    }
    swap(arr[0], arr[l]);
    return l;
}

int partition(int arr[], int n) {
    int l = 0, r = n;
    while (true) {
        while (++l < n && arr[l] < arr[0]);
        while (arr[--r] > arr[0]);
        if (l >= r) break;
        swap(arr[l], arr[r]);
    }
    swap(arr[0], arr[r]);
    return r;
}

int partition3(int arr[], int n) {
    int l = 0, r = n - 1;
    int p = arr[0];
    while (l < r) {
        while (r > l && arr[r] >= p) r--;
        arr[l] = arr[r];
        while (r > l && arr[l] <= p) l++;
        arr[r] = arr[l];
    }
    arr[l] = p;
    return l;
}

int quickSelect(int arr[], int n, int k) {
    int p = partition3(arr, n);
    if (p == k - 1) return arr[p];
    else if (p < k - 1) {
        return quickSelect(arr + p + 1, n - p - 1, k - p - 1);
    } else {
        return quickSelect(arr, p, k);
    }
}

“五分化中项的中项”划分法：

• 将输入数组的N个元素划分为[n/5]组，最后一个组剩下的n mod5组成；
• 寻找每一组的中位数：首先对每组的元素进行插入排序，排序后选出一些中位数；这样可以确保，对于这一些中位数，大于它们的数的个数约等于小于它们的数的个数；
• 对找出的[n/5]个中位数，继续递归找到其中位数，作为最终的pivot；
• 基于pivot进行partition划分；