题解 | #牛群中的第 k 小牛#

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @param k int整型
     * @return int整型
     */
    int findKthSmallest(vector<int>& nums, int k) {
        // write code here
        this->k = k - 1;
        a = nums;
        quickSelect(0, a.size() - 1);
        return a[this->k]; 
    }

    void quickSelect(int l, int r) {
        if (l >= r) return; // 边界
        int mid = divArray(l,  r);
        if (mid == k) return; // 找到第 k 小了
        if (mid > k) quickSelect(l, mid - 1); // 如果 k 在 [l, mid - 1] 内，
        if (mid < k) quickSelect(mid + 1, r); // 如果 k 在 [mid + 1, r] 内，
    }

    // 选择隔板，并将 a[l, r] 沿隔板划分，返回第一个隔板的下标
    int divArray(int l, int r) {
        int div = a[(l + r) / 2]; // 隔板
        int cnt = 0; // 隔板本身的出现次数
        vector<int> lowBuffer, highBuffer; // 比隔板小/大的缓冲区
        for (int i = l; i <= r; ++i) {
            if (a[i] == div) ++cnt;
            else if (a[i] < div) lowBuffer.push_back(a[i]);
            else if (a[i] > div) highBuffer.push_back(a[i]);
        }
        int i = l;
        for (auto p : lowBuffer) a[i++] = p;
        while(cnt-- > 0) a[i++] = div;
        for (auto p : highBuffer) a[i++] = p;
        return l + lowBuffer.size(); // div 的下标
    }

    int k;
    vector<int> a;


};

这才是真正o(n)的算法，快排是o(nlogn)