题目形容

题目链接：https://leetcode-cn.com/probl...
在未排序的数组中找到第 k 个最大的元素。请留神，你须要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例1：
输出: [3,2,1,5,6,4] 和 k = 2
输入: 5
示例2：
输出: [3,2,3,1,2,4,5,5,6] 和 k = 4
输入: 4

常见面试题，去年的面试问的简直都是口述思路，较少实现。支流思路是利用堆排序、疾速排序找出第K大的元素。应用优先队列也可实现指标。

堆排序法

void create(vector<int>& nums, int n) {        for(int i = (n-1)/2; i >= 0; --i){            adjust(nums, n, i);        }    }    void adjust(vector<int>& nums, int n, int root) {        int i = root;        int child = i*2+1;        while(child <= n) {            if(child+1 <= n && nums[child] > nums[child+1]) ++child;            if(nums[child] >= nums[i])break;            swap(nums[i], nums[child]);            i = child;            child = child*2+1;        }    }    int findKthLargest(vector<int>& nums, int k) {        int len = nums.size();        create(nums, k-1);        for(int i = k; i< len; ++i) {            if(nums[i] <= nums[0]) continue;            swap(nums[i], nums[0]);            adjust(nums, k-1, 0);        }        return nums[0];    }

首先须要记住：在建堆的时候调整办法通常是向下调整。用堆排序解决这个问题能够优化的中央就是只建大小为K的小顶堆，之后遍历残余的数，若比堆顶元素大，则替换两个数，再调整堆。
工夫复杂度：建堆工夫复杂度为O(k)，而后续最多经验n-k次调整，每次调整的工夫复杂度为logk，因而工夫复杂度为O(nlogk)
空间复杂度显然为O(1)

为什么建堆的工夫复杂度为O(n)？
由建堆算法可知，数组中每个非叶子节点都要进行一次向下调整算法，在向下调整算法中替换的次数相当于从该节点到叶子节点的高度，那么每一层中所有节点替换的次数为该层节点的个数乘以该节点到叶子节点的高度，比方，第一层的替换次数就是20 h，那么对其进行累计求和，即可失去总的替换次数S(n) = 20 h + 21 (h-1) + 22 (h - 2) + …… + 2h-2 2 +2h-1 1+ 2h * 0 = 2h+1 - (h + 2) = n - log2(n + 1)。因而，工夫复杂度为O(n)

疾速排序法

int partition(vector<int>&nums, int l, int r) {        int i = rand() % (r - l + 1) + l;        swap(nums[i], nums[l]);        int pivotkey = nums[l];        while(l < r) {            while(l < r && pivotkey >= nums[r]) r--;            swap(nums[l], nums[r]);            while(l < r && pivotkey <= nums[l]) l++;            swap(nums[l], nums[r]);        }        return l;    }    int findKthLargest(vector<int>& nums, int k) {        int left = 0, right = nums.size()-1;        int index = partition(nums, left, right);        while(index != k-1) {            if(index < k-1) {                left = index + 1;            }            else {                right = index - 1;            }            index = partition(nums, left, right);        }        return nums[index];    }

因为快排每次确定一个数的最终地位，而此题最终目标是找到第K个最大值，因而咱们做降序排序，每次确定一个index上的数，如果这个index<k，则阐明咱们要找的数在左边，所以只须要做左边的partition；同理，如果index>k，则阐明要找的数在右边，做右边的partition。
工夫复杂度：O(nlogn)
空间复杂度：O(1)

家喻户晓，当原序列有序时，快排效率会进化到O(n²)，因而在partition前退出随机值随机选取中枢值，能够无效防止算法进化。

优先队列法

int findKthLargest(vector<int>& nums, int k) {        priority_queue<int, vector<int>, greater<int> > q;        for(int i = 0; i < k; ++i) {            q.push(nums[i]);        }        int len = nums.size();        for(int i = k; i < len; ++i) {            if(nums[i] > q.top()) {                q.pop();                q.push(nums[i]);            }        }        return q.top();    }

事实上思路与堆排序是统一的，只不过用到了STL。（但用官网函数就是快啊……）