LeetCode Q215: Kth Largest Element in an Array

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.

	class Solution {
	public:
	int partition(vector<int>& nums, int left, int right) {
	int pivot = nums[left];
	int l = left + 1, r = right;
	while (l <= r) {
	if (nums[l] < pivot && nums[r] > pivot)
	swap(nums[l++], nums[r--]);
	if (nums[l] >= pivot) l++;
	if (nums[r] <= pivot) r--;
	}
	swap(nums[left], nums[r]);
	return r;
	}
	int findKthLargest(vector<int>& nums, int k) {
	int left = 0, right = nums.size() - 1;
	while (true) {
	int pos = partition(nums, left, right);
	if (pos == k - 1) return nums[pos];
	if (pos > k - 1) right = pos - 1;
	else left = pos + 1;
	}
	}
	};

view raw gistfile1.txt hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int partition(vector<int>& nums, int left, int right){
	int pivot = nums[right];
	int low = left;
	for(int i=left; i<=right-1; i++){
	if(nums[i]>pivot)
	swap(nums[i], nums[low++]);
	}
	swap(nums[right], nums[low]);
	return low;
	}
	int findKthLargest(vector<int>& nums, int k) {
	if(nums.empty()||k>nums.size())
	return -1;
	int idx=-1;
	int left = 0, right = nums.size()-1;
	while(idx!=k-1){
	idx = partition(nums, left, right);
	if(idx>k-1)
	right=idx-1;
	if(idx<k-1){
	left=idx+1;
	}
	}
	return nums[idx];
	}
	};

view raw Q215Rnd2.cpp hosted with ❤ by GitHub