-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path215_3.py
More file actions
30 lines (23 loc) · 846 Bytes
/
Copy path215_3.py
File metadata and controls
30 lines (23 loc) · 846 Bytes
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
class Solution(object):
def findKthLargest(self, nums, k):
self.buildMinHeap(nums, k)
print nums
for i in range(k, len(nums)):
if nums[i] > nums[0]:
nums[0], nums[i] = nums[i], nums[0]
self.minHeapify(nums, 0, k)
return nums[0]
def minHeapify(self, nums, idx, k):
lson = idx * 2 + 1
rson = idx * 2 + 2
smallest = idx
if lson < k and nums[lson] < nums[idx]:
smallest = lson
if rson < k and nums[rson] < nums[smallest]:
smallest = rson
if smallest != idx:
nums[smallest], nums[idx] = nums[idx], nums[smallest]
self.minHeapify(nums, smallest, k)
def buildMinHeap(self, nums, k):
for i in range(k >> 1, -1, -1):
self.minHeapify(nums, i, k)