215[Medium]:Kth Largest Element in an Array

Part1:问题描述

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.

Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Part2:解题思路

排序取对应的下标即可。排序中当属快排最优（快排也是典型的分治思想），所以选择快排来进行排序。由于我是按照升序进行排列，且vector下标从0到vector.size() - 1，所以对排好序的vector下标为vector.size() - k的元素即为题目所求的第K大的元素。

快排例解：

1.设置2个指针begin和end。将需要排序的数组的开始下标赋给begin，截止下标赋给end。

2.我选取数组第一个元素作为数组划分的参考数据变量pivotkey。

3.首先从end所指位置向begin方向搜索直到找到第一个小于pivotkey的元素，交换end和begin所指的元素，begin后移一位（begin++）

4.从当前begin的位置向end的方向搜索直到找到第一个大于pivotkey的元素，

交换end和begin所指的元素，end前移一位（

end--

）

5.重复步骤3，4直到begin=end为止

做完上述步骤，数组以pivotkey为界，左边一部分的元素都小于pivotkey，右边一部分都大于pivotkey。再不断对左右2边的数组分别进行上述操作（递归）直到使整个数组有序。

Part3:C++代码

#include<iostream>
#include<vector>
using namespace std;

void swap(int& a, int& b) { // 必须传指针或者引用不然调用此函数之后原数组不会有所更改
	int temp;
	temp = a;
	a = b;
	b = temp;
}


int pivotloc(vector<int>& nums, int left, int right) {

        int begin = left, end = right;
	int pivotkey = nums[left];
	while (begin < end) {
		while (nums[end] >= pivotkey && begin < end) {
			end--;
		}
                swap(nums[begin], nums[end]);
	        if (begin < end) begin++;
			
                while (nums[begin] <= pivotkey && begin < end) {
			begin++;
		}
                swap(nums[begin], nums[end]);
		if (begin < end) end--; 
	} 
	return begin;
}


void quickSort(vector<int>& nums, int left, int right) {
	if (left < right) {
	    int pivot = pivotloc(nums, left, right);
	    quickSort(nums, left, pivot - 1);
	    quickSort(nums, pivot + 1, right);
	}
}

int findKthLargest(vector<int>& nums, int k) {
	quickSort(nums, 0, nums.size() - 1);	
	return nums.at(nums.size() - k);
}

int main() {
	int n, temp;
	vector<int> nums;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		nums.push_back(temp);
	}
	int k;
	cin >> k;
	cout << "The " << k << "th largest number is" << " " << findKthLargest(nums, k) << endl;
	cout << "The result of quickSort is ";
	for (int i = 0; i < n; i++) {
		cout << nums[i] << " ";
	}
	return 0;
}