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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Divide and conquer

Sorting

Data structures

Probability

Starter code: class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        

Solutions:
class Solution:

	def findKthLargest(self, nums, k):
		nums = sorted(nums, reverse=True)
		return nums[k - 1]


class Solution:

	def findKthLargest(self, nums, k):
		nums.sort()
		return nums[len(nums) - k]


class Solution:

	def findKthLargest(self, nums, k):
		heap = []
		for num in nums:
			heapq.heappush(heap, num)
		for _ in range(len(nums) - k):
			heapq.heappop(heap)
		return heapq.heappop(heap)


class Solution:

	def findKthLargest(self, nums, k):
		if not nums:
			return -1
		pq = []
		for num in nums:
			if len(pq) < k:
				heapq.heappush(pq, num)
			else:
				popped = heapq.heappop(pq)
				if popped < num:
					heapq.heappush(pq, num)
				else:
					heapq.heappush(pq, popped)
		return heapq.heappop(pq)


class Solution:

	def findKthLargest(self, nums, k):

		def partition(nums, ind, i, j):
			(big, scan) = (i, i)
			(nums[ind], nums[j]) = (nums[j], nums[ind])
			while scan < j:
				if nums[scan] > nums[j]:
					(nums[big], nums[scan]) = (nums[scan], nums[big])
					big += 1
				scan += 1
			(nums[j], nums[big]) = (nums[big], nums[j])
			return big
		(i, j) = (0, len(nums) - 1)
		while i <= j:
			ind = random.randint(i, j)
			new_ind = partition(nums, ind, i, j)
			if new_ind == k - 1:
				return nums[new_ind]
			elif new_ind < k - 1:
				i = new_ind + 1
			else:
				j = new_ind - 1
		return -1


class Solution:

	def findKthLargest(self, nums, k):
		sor = sorted(nums)
		lenn = len(nums)
		return sor[lenn - 1 - (k - 1)]


class Solution:

	def findKthLargest(self, nums, k):
		return sorted(nums)[len(nums) - k]


class Solution:

	def swap(self, A, i, j):
		if A[i] != A[j]:
			(A[i], A[j]) = (A[j], A[i])

	def partition(self, A, p, r):
		self.swap(A, r, random.randint(p, r))
		x = A[r]
		j = p - 1
		for i in range(p, r):
			if A[i] <= x:
				j += 1
				self.swap(A, i, j)
		j += 1
		self.swap(A, r, j)
		return j

	def findElement(self, A, k):
		(low, high) = (0, len(A) - 1)
		while low < high:
			i = self.partition(A, low, high)
			if i > k:
				high = i - 1
			elif i < k:
				low = i + 1
			else:
				return A[k]
		return A[k]

	def findKthLargest(self, nums, k):
		return self.findElement(nums, len(nums) - k)