LeetCode 215 Kth Largest Element in an Array

LeetCode

Given an integer array nums and an integer k, return the k<sup>th</sup> largest element in the array.

Note that it is the k<sup>th</sup> largest element in the sorted order, not the k<sup>th</sup> distinct element.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

1 <= k <= nums.length <= 10<sup>4</sup> -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

题目大意：

求第k大的数(1th index)

Heap算法思路：

求第k个最大也就是用最小堆(大->小)

注意事项：

N/A

Python代码：

def findKthLargest(self, nums: List[int], k: int) -> int:
	res = []  # min heap
	for i in range(len(nums)):
		if i < k:
			heapq.heappush(res, nums[i])
		elif nums[i] > res[0]:
			heapq.heapreplace(res, nums[i])
	return res[0]

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(k)

---

Quickselect算法II解题思路：

N/A

注意事项：

1. 递归调用仍用m，而不是跟pivot_pos相关，因为m是下标位置
2. partition中range用[start, end)而不是len

Python代码：

def findKthLargest(self, nums: List[int], k: int) -> int:
	m = len(nums) - k
	return self.quick_select(nums, 0, len(nums) - 1, m)

def quick_select(self, nums, start, end, m):
	if start > end:
		return -1
	pivot_pos = self.partition(nums, start, end)
	if m == pivot_pos:
		return nums[pivot_pos]
	elif m < pivot_pos:
		return self.quick_select(nums, start, pivot_pos - 1, m)
	else:
		return self.quick_select(nums, pivot_pos + 1, end, m)  # remember use m not related to pivot_pos

def partition(self, nums, start, end):
	pivot, no_smaller_index = nums[end], start
	for i in range(start, end):  # remember use start and end not len
		if nums[i] < pivot:
			nums[i], nums[no_smaller_index] = nums[no_smaller_index], nums[i]
			no_smaller_index += 1
	nums[no_smaller_index], nums[end] = nums[end], nums[no_smaller_index]
	return no_smaller_index

算法分析：

T(n) = T(n/2)+n, 时间复杂度为O(n)，空间复杂度O(1)

---

排序算法III解题思路：

先排序

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(1)