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.
- You may assume k is always valid, 1 ≤ k ≤ array's length.
For example:
- Given
3,2,1,5,6,4andk = 2, return5.
C Solution:
void insert(int *heap, int *top, int val, int k) {
if (*top < k + 1) {
heap[(*top)++] = val;
int cur = *top - 1, root = cur / 2;
while (root && heap[root] > heap[cur]) {
int tmp = heap[root];
heap[root] = heap[cur];
heap[cur] = tmp;
cur = root;
root = cur / 2;
}
return;
}
if (val <= heap[1]) return;
heap[1] = val;
int cur = 1, left = 2;
while (left < *top) {
if (left + 1 < *top && heap[left + 1] < heap[left]) left++;
if (heap[cur] <= heap[left]) break;
int tmp = heap[cur];
heap[cur] = heap[left];
heap[left] = tmp;
cur = left;
left = 2 * cur;
}
}
int findKthLargest(int* nums, int numsSize, int k) {
int *heap = malloc((k + 1) * sizeof(int)), top = 1;
int i;
for (i = 0; i < numsSize; i++) {
insert(heap, &top, nums[i], k);
}
return heap[1];
}
Python Solution 1:
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums.sort(reverse = True)
return nums[k - 1]
Python Solution 2:
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums = [-num for num in nums]
heapq.heapify(nums)
while k > 1:
heapq.heappop(nums)
k -= 1
return -heapq.heappop(nums)
Python Solution 3:
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, num)
return heap[0]
Summary:
- This problem can be solved in many ways.
- sort first, then return the kth elements. O(N * lg(N)) time and O(1) space
- heap. O(N * lg(K)) time and O(K) space
- divide and conquer. check O(N) best case / O(N2) worst case time and O(1) space.
- Partition-based selection can get an average O(N) time complexity.
LeetCode: 215. Kth Largest Element in an Array
近期评论