forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0215-kth-largest-element-in-an-array.py
46 lines (37 loc) · 1.17 KB
/
0215-kth-largest-element-in-an-array.py
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
36
37
38
39
40
41
42
43
44
45
46
# Solution: Sorting
# Time Complexity:
# - Best Case: O(n)
# - Average Case: O(n*log(n))
# - Worst Case:O(n*log(n))
# Extra Space Complexity: O(n)
class Solution1:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums.sort()
return nums[len(nums) - k]
# Solution: QuickSelect
# Time Complexity:
# - Best Case: O(n)
# - Average Case: O(n)
# - Worst Case: O(n^2)
# Extra Space Complexity: O(1)
class Solution2:
def partition(self, nums: List[int], left: int, right: int) -> int:
pivot, fill = nums[right], left
for i in range(left, right):
if nums[i] <= pivot:
nums[fill], nums[i] = nums[i], nums[fill]
fill += 1
nums[fill], nums[right] = nums[right], nums[fill]
return fill
def findKthLargest(self, nums: List[int], k: int) -> int:
k = len(nums) - k
left, right = 0, len(nums) - 1
while left < right:
pivot = self.partition(nums, left, right)
if pivot < k:
left = pivot + 1
elif pivot > k:
right = pivot - 1
else:
break
return nums[k]