215 Kth Largest Element in an Array

Search…

215. Kth Largest Element in an Array​
1. Question
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.
For example,
Given[3,2,1,5,6,4]and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
2. Implementation
(1) Quick Select
1
class Solution {
2
    public int findKthLargest(int[] nums, int k) {
3
        return getKthNum(nums, 0, nums.length - 1, k - 1);
4
    }
5
​
6
    public int getKthNum(int[] nums, int start, int end, int k) {
7
        int pivot = partition(nums, start, end);
8
​
9
        if (pivot < k) {
10
            return getKthNum(nums, pivot + 1, end, k);
11
        }
12
        else if (pivot > k) {
13
            return getKthNum(nums, start, pivot - 1, k);
14
        }
15
        else {
16
            return nums[pivot];
17
        }
18
    }
19
​
20
    public int partition(int[] nums, int start, int end) {
21
        int mid = start + (end - start) / 2;
22
​
23
        swap(nums, mid, end);
24
​
25
        for (int i = start; i < end; i++) {
26
            if (nums[i] > nums[end]) {
27
                swap(nums, i, start);
28
                ++start;
29
            }
30
        }
31
​
32
        swap(nums, start, end);
33
        return start;
34
    }
35
​
36
    public void swap(int[] nums, int i, int j) {
37
        int temp = nums[i];
38
        nums[i] = nums[j];
39
        nums[j] = temp;
40
    }
41
}
Copied!
(2) Heap
1
class Solution {
2
    public int findKthLargest(int[] nums, int k) {
3
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
4
​
5
        for (int num : nums) {
6
            minHeap.add(num);
7
​
8
            if (minHeap.size() > k) {
9
                minHeap.remove();
10
            }
11
        }
12
        return minHeap.peek();
13
    }
14
}
Copied!
3. Time & Space Complexity
Quick Select: 时间复杂度O(n), 空间复杂度O(1)
Heap: 时间复杂度O(n), 空间复杂度O(k)

Heap

239 Sliding Window Maximum

Last modified 2yr ago

Copy link

Contents

215. Kth Largest Element in an Array

1. Question

2. Implementation

3. Time & Space Complexity

215. Kth Largest Element in an Array​

1. Question

2. Implementation

3. Time & Space Complexity

215. Kth Largest Element in an Array