分治算法（三）215. Kth Largest Element in an Array【middle】03-04

1、题目

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.

For example,Given [3,2,1,5,6,4] and k = 2, return 5.

2、解题思路

第i大，换句话就是，除去第1～第（i－1）后的第一大数。本质上，是一个递归的求数组最大元素的算法（分治体现）。找出数组最大元素，与数组最后一个元素交换，第二次从0～size－2找最大元素，与倒数第二个交换次序，循环i次后停止，返回［size－i］即为第i大元素

3、代码如下

class Solution {public:    void findBigest(vector<int>& nums, int size) {	int large = nums[0];	int index = 0;	for (int i = 0; i < size; i++) {		if (nums[i] > large) {			large = nums[i];			index = i;		}	}	int temp = nums[size - 1];	nums[size - 1] = large;	nums[index] = temp;}    int findKthLargest(vector<int>& nums, int k) {        for (int i = 0; i < k; i++) {		findBigest(nums, nums.size() - i);	}	return nums[nums.size() - k];    }};