本文主要是介绍LeetCode 215. Kth Largest Element in an Array（数组中的第K个最大元素），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
在未排序的数组中找到第 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 总是有效的，且 1 ≤ k ≤ 数组的长度。
思路：
最简单最直接的做法，就是先将数组从小到大排序，然后从后往前搜索数组中第k大的元素，当然这样做非常费时。
我们可以用快速排序的思想：
（1）选中数组中的一个元素作为支点，将小于该支点的所有元素放到其左侧，大于该支点的所有元素放到其右侧，如果该支点的右边恰巧有k-1个元素，那么这个支点就是我们要找的答案；
（2）如果支点右侧区域的元素个数大于k-1，说明我们要找的目标元素在支点的右侧，因此在右侧区域重新选择新支点，同时，目标元素依然是右侧区域的第k个最大的元素；
同理，如果支点右侧区域的元素个数小于k-1，假设为j-1，说明我们要找的目标元素在支点的左侧，因此在左侧区域重新选择新支点，而此时，目标元素是左侧区域的第k-j个最大的元素；
（3）更新支点和k值，重复步骤（1）（2），直到得到我们想要的答案
我们利用交换思想达到分治的目的，将问题范围缩小，宏观有序，微观无序，避免将数组中的所有元素排序，从而提到计算效率。
实现（C++）:
方法1：暴力排序
class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int i;for(i=nums.size()-1; i>=nums.size()-k+1; i--){}return nums[i];}
};
方法2：分治
class Solution {public:int find(vector<int>& nums, int k, int begin, int end, int pivot){ //分治，交换排序，快速排序//nums：目标数组//k：寻找第k个大的元素//begin：寻找区域的起点//end：寻找区域的终点//pivot：支点if(begin==end)return nums[begin];int i=begin;int j=end;while(i<j){ //交换：将小于支点的元素放到其左侧，大于支点的元素放到其右侧while(i<j&&nums[j]>=pivot)j--;nums[i]=nums[j];while(i<j&&nums[i]<=pivot)i++;nums[j]=nums[i];}nums[i]=pivot; if(end-j==k-1) //如果支点右侧恰巧有k-1个元素，说明该支点就是我们要找的目标元素return nums[j];else if(end-j>k-1&&j+1<=end) //如果支点右侧区域的元素个数大于k-1，则继续在右侧区域寻找目标元素return find(nums, k, j+1, end, nums[j+1]);else if(end-j<k-1&&j-1>=begin) //如果支点右侧区域的元素个数小于k-1，则继续在左侧区域寻找目标元素return find(nums, k-(end-j)-1, begin, j-1, nums[begin]);return -1;}public:int findKthLargest(vector<int>& nums, int k) {int begin=0;int end=nums.size()-1;int pivot=nums[0];return find(nums, k, begin, end, pivot); }
};
这篇关于LeetCode 215. Kth Largest Element in an Array（数组中的第K个最大元素）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
