215. Kth Largest Element in an Array

  • 38.2%

https://leetcode.com/problems/kth-largest-element-in-an-array/#/description

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.

1
2
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.


总结:

方法一 :

先排序,后选出第k大的数字。面试肯定没啥用。

注意,对nums排序是,sort(nums.begin(), nums.end()), 不是sort(nums)

1
2
3
4
5
6
7
8
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
sort(nums.begin(), nums.end());
return nums[n - k];
}
};

我的代码实现:

1
2
3
4
5
6
7
8
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
return nums[n-k];
}
};

方法二:

求最大k值,建最小堆,效率O(nlogk),第一次建堆k,每次排除一个头部,并重新维护堆性质logk。

学习如何建堆,默认建最大堆,如何建立最小堆。同时make_heap(res.begin(), res.end()),而不是make_heap(res), 类似于sort。

学习如何设置cmp函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res(nums.begin(), nums.begin() + k);
make_heap(res.begin(), res.end(), [](int& a, int& b) { return a>b; });
for (int i = k; i<n; i++) {
if (nums[i]>res[0]) {
pop_heap(res.begin(), res.end(), [](int& a, int& b) { return a>b; });
res.pop_back();
res.push_back(nums[i]);
push_heap(res.begin(), res.end(), [](int& a, int& b) { return a>b; });
}
}
sort_heap(res.begin(), res.end(), [](int& a, int& b) { return a>b; });
return res[k-1];
}
};

我的实现

需要先建最小堆, 然后从k至最后遍历

如果大于最小值,替换了,然后维护最小堆的性质

遍历到最后,堆里面是最大的k个,堆的root是第k大的值。

返回res[0]就好。

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
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
if(nums.size()<k) return -1;
// make heap
vector<int> res(nums.begin(), nums.begin()+k);
for(int i=(k-2)/2; i>=0; i--){
minHeapify(res, i, k-1);
}
for(int i=k; i<nums.size(); i++){
if(nums[i]>res[0]){
res[0] = nums[i];
minHeapify(res, 0, k-1);
}
}
return res[0];
}

void minHeapify(vector<int>& nums, int start, int end){
if(start>=end) return;
int parent = start;
int child = 2*parent+1;
while(child<=end){
if(child+1<=end && nums[child+1]<nums[child]){
child += 1;
}
if(nums[child]<nums[parent]){
swap(nums[child], nums[parent]);
parent = child;
child = 2*parent+1;
}else{
break;
}
}
return;
}
};

我的代码实现:

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 {
public:
int findKthLargest(vector<int>& nums, int k) {
vector<int> v(nums.begin(), nums.begin()+k);
for(int i=(k-2)/2; i>=0; i--)
miniheapify(v, i, k-1);
for(int i=k; i<nums.size(); i++)
if(nums[i]>v[0]){
v[0] = nums[i];
miniheapify(v, 0, k-1);
}
return v[0];
}

void miniheapify(vector<int>& v, int start, int end){
if(start>=end)
return;
int parent = start, child = 2*parent+1;
while(child<=end){
if(child+1<=end && v[child+1]<v[child])
child += 1;
if(v[child]<v[parent]){
swap(v[child], v[parent]);
parent = child;
child = 2*parent+1;
}else
break;
}
}
};

方法三:

使用快排里的patition方法,直到分配到一遍的是k个,并且对此进行排序。

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
class Solution { 
public:
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[left];
int l = left + 1, r = right;
while (l <= r) {
if (nums[l] < pivot && nums[r] > pivot)
swap(nums[l++], nums[r--]);
if (nums[l] >= pivot) l++;
if (nums[r] <= pivot) r--;
}
swap(nums[left], nums[r]);
return r;
}

int findKthLargest(vector<int>& nums, int k) {
int left = 0, right = nums.size() - 1;
while (true) {
int pos = partition(nums, left, right);
if (pos == k - 1) return nums[pos];
if (pos > k - 1) right = pos - 1;
else left = pos + 1;
}
}
};

我的代码实现:

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
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int left=0, right = nums.size()-1;
int index = partition(nums, left, right);
while(index!=k-1){ // 这里是k-1,而不是k,求第k,就是index==k-1
if(index<k-1){
left = index+1;
}else{
right = index-1;
}
index = partition(nums, left, right);
}
return nums[k-1];
}

int partition(vector<int>& nums, int left, int right){
if(left == right)
return left;
int pos = left-1;
for(int i=left; i < right; i++){
if(nums[i]>=nums[right]){
pos++;
swap(nums[pos], nums[i]);
}
}
pos++;
swap(nums[pos], nums[right]);
return pos;
}
};

我的代码实现:

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
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int n = nums.size();
int left = 0, right = n-1;
int pos = partition(nums, left, right);
while(pos!=n-k){
if(pos<n-k)
left = pos+1;
else
right = pos-1;
pos = partition(nums, left, right);
}
return nums[n-k];
}

int partition(vector<int>& nums, int left, int right){
if(left>=right)
return left;
int pos = left-1;
for(int i=left; i<right; i++)
if(nums[i]<=nums[right])
swap(nums[i], nums[++pos]);
swap(nums[right], nums[++pos]);
return pos;
}
};

资料,如何设置最小堆的比较函数

http://stackoverflow.com/questions/14016921/comparator-for-min-heap-in-c

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
#include <vector>
#include <algorithm>
#include <iostream>

struct greater1{
bool operator()(const long& a,const long& b) const{
return a>b;
}
};

int main() {
std::vector<long> humble;
humble.push_back(15);
humble.push_back(15);
humble.push_back(9);
humble.push_back(25);

std::make_heap(humble.begin(), humble.end(), greater1());
while (humble.size()) {
std::pop_heap(humble.begin(),humble.end(),greater1());
long min = humble.back();
humble.pop_back();
std::cout << min << std::endl;
}

return 0;
}

cpp


https://discuss.leetcode.com/topic/15256/4-c-solutions-using-partition-max-heap-priority_queue-and-multiset-respectively

4 C++ Solutions using Partition, Max-Heap, priority_queue and multiset respectively

Well, this problem has a naive solution, which is to sort the array in descending order and return the k-1-th element.

1
2
3
4
5
6
7
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[k - 1];
}
};

However, sorting algorithm gives O(nlogn) complexity. Suppose n = 10000 and k = 2, then we are doing a lot of unnecessary operations. In fact, this problem has at least two simple and faster solutions.

Well, the faster solution has no mystery. It is also closely related to sorting. I will give two algorithms for this problem below, one using quicksort(specifically, the partition subroutine) and the other using heapsort.

Quicksort

In quicksort, in each iteration, we need to select a pivot and then partition the array into three parts:

  1. Elements smaller than the pivot;
  2. Elements equal to the pivot;
  3. Elements larger than the pivot.

Now, let’s do an example with the array [3, 2, 1, 5, 4, 6] in the problem statement. Let’s assume in each time we select the leftmost element to be the pivot, in this case, 3. We then use it to partition the array into the above 3 parts, which results in [1, 2, 3, 5, 4, 6]. Now 3 is in the third position and we know that it is the third smallest element. Now, do you recognize that this subroutine can be used to solve this problem?

In fact, the above partition puts elements smaller than the pivot before the pivot and thus the pivot will then be the k-th smallest element if it is at the k-1-th position. Since the problem requires us to find the k-th largest element, we can simply modify the partition to put elements larger than the pivot before the pivot. That is, after partition, the array becomes [5, 6, 4, 3, 1, 2]. Now we know that 3 is the 4-th largest element. If we are asked to find the 2-th largest element, then we know it is left to 3. If we are asked to find the 5-th largest element, then we know it is right to 3. So, in the average sense, the problem is reduced to approximately half of its original size, giving the recursion T(n) = T(n/2) + O(n) in which O(n) is the time for partition. This recursion, once solved, gives T(n) = O(n) and thus we have a linear time solution. Note that since we only need to consider one half of the array, the time complexity is O(n). If we need to consider both the two halves of the array, like quicksort, then the recursion will be T(n) = 2T(n/2) + O(n) and the complexity will be O(nlogn).

Of course, O(n) is the average time complexity. In the worst case, the recursion may become T(n) = T(n - 1) + O(n) and the complexity will be O(n^2).

Now let’s briefly write down the algorithm before writing our codes.

  1. Initialize left to be 0 and right to be nums.size() - 1;
  2. Partition the array, if the pivot is at the k-1-th position, return it (we are done);
  3. If the pivot is right to the k-1-th position, update right to be the left neighbor of the pivot;
  4. Else update left to be the right neighbor of the pivot.
  5. Repeat 2.

Now let’s turn it into code.

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
class Solution { 
public:
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[left];
int l = left + 1, r = right;
while (l <= r) {
if (nums[l] < pivot && nums[r] > pivot)
swap(nums[l++], nums[r--]);
if (nums[l] >= pivot) l++;
if (nums[r] <= pivot) r--;
}
swap(nums[left], nums[r]);
return r;
}

int findKthLargest(vector<int>& nums, int k) {
int left = 0, right = nums.size() - 1;
while (true) {
int pos = partition(nums, left, right);
if (pos == k - 1) return nums[pos];
if (pos > k - 1) right = pos - 1;
else left = pos + 1;
}
}
};

Heapsort

Well, this problem still has a tag “heap”. If you are familiar with heapsort, you can solve this problem using the following idea:

  1. Build a max-heap for nums, set heap_size to be nums.size();
  2. Swap nums[0] (after buding the max-heap, it will be the largest element) with nums[heap_size - 1] (currently the last element). Then decrease heap_size by 1 and max-heapify nums (recovering its max-heap property) at index 0;
  3. Repeat 2 for k times and the k-th largest element will be stored finally at nums[heap_size].

Now I paste my code below. If you find it tricky, I suggest you to read the Heapsort chapter of Introduction to Algorithms, which has a nice explanation of the algorithm. My code simply translates the pseudo code in that book :-)

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
class Solution {
public:
inline int left(int idx) {
return (idx << 1) + 1;
}
inline int right(int idx) {
return (idx << 1) + 2;
}
void max_heapify(vector<int>& nums, int idx) {
int largest = idx;
int l = left(idx), r = right(idx);
if (l < heap_size && nums[l] > nums[largest]) largest = l;
if (r < heap_size && nums[r] > nums[largest]) largest = r;
if (largest != idx) {
swap(nums[idx], nums[largest]);
max_heapify(nums, largest);
}
}
void build_max_heap(vector<int>& nums) {
heap_size = nums.size();
for (int i = (heap_size >> 1) - 1; i >= 0; i--)
max_heapify(nums, i);
}
int findKthLargest(vector<int>& nums, int k) {
build_max_heap(nums);
for (int i = 0; i < k; i++) {
swap(nums[0], nums[heap_size - 1]);
heap_size--;
max_heapify(nums, 0);
}
return nums[heap_size];
}
private:
int heap_size;
}

If we are allowed to use the built-in priority_queue, the code will be much more shorter :-)

1
2
3
4
5
6
7
8
9
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
for (int i = 0; i < k - 1; i++)
pq.pop();
return pq.top();
}
};

Well, the priority_queue can also be replaced by multiset :-)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int> mset;
int n = nums.size();
for (int i = 0; i < n; i++) {
mset.insert(nums[i]);
if (mset.size() > k)
mset.erase(mset.begin());
}
return *mset.begin();
}
};

https://discuss.leetcode.com/topic/16970/4ms-c-solution-straightforward-to-find-largest-k-kind-like-a-partition-version

4ms c++ solution. straightforward to find largest k. kind like a partition version.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int cur=nums[k-1];
vector<int> bigger;
vector<int> smaller;
for(size_t i=0; i<nums.size(); ++i){
if(i==k-1) continue;
if(nums[i]>=cur) bigger.push_back(nums[i]);
else smaller.push_back(nums[i]);
}
if(bigger.size()==k-1) return cur;
if(bigger.size()>k-1) return findKthLargest(bigger,k);
if(bigger.size()<k-1) return findKthLargest(smaller,k-bigger.size()-1);
}
};

https://discuss.leetcode.com/topic/22159/python-different-solutions-with-comments-bubble-sort-selection-sort-heap-sort-and-quick-sort

Python different solutions with comments (bubble sort, selection sort, heap sort and quick sort).

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# O(nlgn) time
def findKthLargest1(self, nums, k):
return sorted(nums, reverse=True)[k-1]

# O(nk) time, bubble sort idea, TLE
def findKthLargest2(self, nums, k):
for i in xrange(k):
for j in xrange(len(nums)-i-1):
if nums[j] > nums[j+1]:
# exchange elements, time consuming
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums[len(nums)-k]

# O(nk) time, selection sort idea
def findKthLargest3(self, nums, k):
for i in xrange(len(nums), len(nums)-k, -1):
tmp = 0
for j in xrange(i):
if nums[j] > nums[tmp]:
tmp = j
nums[tmp], nums[i-1] = nums[i-1], nums[tmp]
return nums[len(nums)-k]

# O(k+(n-k)lgk) time, min-heap
def findKthLargest4(self, nums, k):
heap = []
for num in nums:
heapq.heappush(heap, num)
for _ in xrange(len(nums)-k):
heapq.heappop(heap)
return heapq.heappop(heap)

# O(k+(n-k)lgk) time, min-heap
def findKthLargest5(self, nums, k):
return heapq.nlargest(k, nums)[k-1]

# O(n) time, quick selection
def findKthLargest(self, nums, k):
# convert the kth largest to smallest
return self.findKthSmallest(nums, len(nums)+1-k)

def findKthSmallest(self, nums, k):
if nums:
pos = self.partition(nums, 0, len(nums)-1)
if k > pos+1:
return self.findKthSmallest(nums[pos+1:], k-pos-1)
elif k < pos+1:
return self.findKthSmallest(nums[:pos], k)
else:
return nums[pos]

# choose the right-most element as pivot
def partition(self, nums, l, r):
low = l
while l < r:
if nums[l] < nums[r]:
nums[l], nums[low] = nums[low], nums[l]
low += 1
l += 1
nums[low], nums[r] = nums[r], nums[low]
return low

https://discuss.leetcode.com/topic/20740/share-my-python-solution-with-quickselect-idea

Share my Python solution with QuickSelect idea

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @return {integer}
def findKthLargest(self, nums, k):
# QuickSelect idea: AC in 52 ms
# ---------------------------
#
pivot = nums[0]
left = [l for l in nums if l < pivot]
equal = [e for e in nums if e == pivot]
right = [r for r in nums if r > pivot]

if k <= len(right):
return self.findKthLargest(right, k)
elif (k - len(right)) <= len(equal):
return equal[0]
else:
return self.findKthLargest(left, k - len(right) - len(equal))

cpp

Solution 1:

20ms, 53,47%, June.18th, 2016

https://leetcode.com/discuss/38336/solutions-partition-priority_queue-multiset-respectively

1
2
3
4
5
6
7
8
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int N = nums.size();
sort(nums.begin(), nums.end());
return nums[N-k];
}
};

python

Solution Mine:

52ms, 88.30%, June.18th, 2016

1
2
3
4
5
6
7
8
9
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums.sort()
return nums[-k]

Solution 1:

3164ms, 7.6%, June.18th, 2016

https://leetcode.com/discuss/50389/share-my-python-solution-with-quickselect-idea

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
pivot = nums[0]
left = [i for i in nums if i < pivot]
equal = [i for i in nums if i == pivot]
right = [i for i in nums if i > pivot]

if k <= len(right):
return self.findKthLargest(right, k)
elif k <= len(right) + len(equal):
return equal[0]
else:
return self.findKthLargest(left, k - len(right)-len(equal))

Solution 2:

60ms, 75.44%, June.18th, 2016

https://leetcode.com/discuss/53530/python-different-solutions-comments-bubble-selection-quick

1
2
3
4
5
6
7
8
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
return heapq.nlargest(k, nums)[k-1]

6ms, 72.82%, June.18th, 2016

1
2
3
4
5
6
7
8
https://leetcode.com/discuss/36966/solution-explained
public class Solution {
public int findKthLargest(int[] nums, int k) {
final int N = nums.length;
Arrays.sort(nums);
return nums[N-k];
}
}

java


https://discuss.leetcode.com/topic/14597/solution-explained

Solution explained

This problem is well known and quite often can be found in various text books.

You can take a couple of approaches to actually solve it:

  • O(N lg N) running time + O(1) memory

The simplest approach is to sort the entire input array and then access the element by it’s index (which is O(1)) operation:

1
2
3
4
5
public int findKthLargest(int[] nums, int k) {
final int N = nums.length;
Arrays.sort(nums);
return nums[N - k];
}
  • O(N lg K) running time + O(K) memory

Other possibility is to use a min oriented priority queue that will store the K-th largest values. The algorithm iterates over the whole input and maintains the size of priority queue.

1
2
3
4
5
6
7
8
9
10
11
12
public int findKthLargest(int[] nums, int k) {

final PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
pq.offer(val);

if(pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
  • O(N) best case / O(N^2) worst case running time + O(1) memory

The smart approach for this problem is to use the selection algorithm (based on the partion method - the same one as used in quicksort).

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
public int findKthLargest(int[] nums, int k) {

k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}

private int partition(int[] a, int lo, int hi) {

int i = lo;
int j = hi + 1;
while(true) {
while(i < hi && less(a[++i], a[lo]));
while(j > lo && less(a[lo], a[--j]));
if(i >= j) {
break;
}
exch(a, i, j);
}
exch(a, lo, j);
return j;
}

private void exch(int[] a, int i, int j) {
final int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

private boolean less(int v, int w) {
return v < w;
}

O(N) guaranteed running time + O(1) space

So how can we improve the above solution and make it O(N) guaranteed? The answer is quite simple, we can randomize the input, so that even when the worst case input would be provided the algorithm wouldn’t be affected. So all what it is needed to be done is to shuffle the input.

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
public int findKthLargest(int[] nums, int k) {

shuffle(nums);
k = nums.length - k;
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
final int j = partition(nums, lo, hi);
if(j < k) {
lo = j + 1;
} else if (j > k) {
hi = j - 1;
} else {
break;
}
}
return nums[k];
}

private void shuffle(int a[]) {

final Random random = new Random();
for(int ind = 1; ind < a.length; ind++) {
final int r = random.nextInt(ind + 1);
exch(a, ind, r);
}
}

There is also worth mentioning the Blum-Floyd-Pratt-Rivest-Tarjan algorithm that has a guaranteed O(N) running time.

谢谢你,可爱的朋友。