The problem to 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.

Simplest Solution - Sort and Index

The most straightforward solution to this problem is sort and return the $k$ element in the sorted list.

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

The performance is as follows.

The complexity of the time is $O(nlogn)$ and space is $O(1)$. The runtime of the algorithm is not too bad in the testcases.

Partition Solution

As we know, the general complexity of sort algorithm $nlogn$. But we actually dont need the sort the whole list. In this case, we can find any $k$ instead of particular k. Therefore, we can better instead of sorting whole list. One popular sorting algorithm is quick sort. We can look into details of the algorithm.

In quick sort, it keeps partitioning the list based on a pivot. The numbers that are bigger than the pivot will be put in the left $i+1$ and other numbers will be put in the right.
Combining the partition step and binary search, we can keep the process untill the number of left we put in the left is $k$. Here is the implementation.

The complexity if $O(n)$ in time and $O(1)$ in space.

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
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def exchange(nums,a,b):
if nums[a] != nums[b]:
nums[a] = nums[a] ^ nums[b]
nums[b] = nums[a] ^ nums[b]
nums[a] = nums[a] ^ nums[b]

def partition(nums,lo,hi):
pivot = nums[hi]
ii = lo - 1
for jj in xrange(lo,hi):
if nums[jj] > pivot:
ii += 1
exchange(nums,ii,jj)
if nums[hi] > nums[ii+1]:
exchange(nums,ii+1,hi)
return(ii+1)



if len(nums) < k:
return(None)
lo = 0; hi = len(nums) -1
while(lo <= hi):
mid = partition(nums,lo,hi)
if mid == k-1:
return(nums[mid])
elif mid < k-1: #less than k in the left, keep to partition the right
lo = mid + 1
else:
hi = mid - 1
return(nums[lo])

Ganrantee the Average Performance

The common way to avoid the effect of worst cases in sorting can be applied here too. We can randomize the input to avoid the worst case.

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
class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
def exchange(nums,a,b):
if nums[a] != nums[b]:
nums[a] = nums[a] ^ nums[b]
nums[b] = nums[a] ^ nums[b]
nums[a] = nums[a] ^ nums[b]

def partition(nums,lo,hi):
pivot = nums[hi]
ii = lo - 1
for jj in xrange(lo,hi):
if nums[jj] > pivot:
ii += 1
exchange(nums,ii,jj)
if nums[hi] > nums[ii+1]:
exchange(nums,ii+1,hi)
return(ii+1)



if len(nums) < k:
return(None)
random.shuffle(nums)
lo = 0; hi = len(nums) -1
while(lo <= hi):
mid = partition(nums,lo,hi)
if mid == k-1:
return(nums[mid])
elif mid < k-1: #less than k in the left, keep to partition the right
lo = mid + 1
else:
hi = mid - 1
return(nums[lo])

The performance is as follows.

Comments