Coding-Problems/LeetCode/Solutions/LC0215.cpp at master · Natansh2005/Coding-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
Problem Statement: https://leetcode.com/problems/kth-largest-element-in-an-array/
Time: O(n²), average O(n)
Space: O(1)
Author: Mohammed Shoaib, github.com/Mohammed-Shoaib
*/

class Solution {
public:
	int findKthLargest(vector<int>& nums, int k) {
		quick_select(0, nums.size() - 1, --k, nums);
		return nums[k];
	}

	void quick_select(int i, int j, int k, vector<int>& nums) {
		int q = partition(i, j, nums);
		if (q == k)
			return;
		else if (q > k)
			quick_select(i, q - 1, k, nums);
		else
			quick_select(q + 1, j, k, nums);
	}

	int partition(int i, int j, vector<int>& nums) {
		int k = i;
		while (i < j) {
			if (nums[i] > nums[j])
				swap(nums[k++], nums[i]);
			i++;
		}
		swap(nums[k], nums[j]);
		return k;
	}
};