The worst linear time algorithm?

Today we have a common problem, finding the kth largest element in an array. We need to find the kth largest element after sorting the array. And we need to solve the time in linear time.

Problem definition

Input:

A array of n integers and an integer k (1 ≤ k ≤ n).

Output:

The kth largest element in the array.

Example:

Input: [3, 2, 1, 5, 6, 4], k = 2    Output: 5

Approach

The most common algorithm to solve this problem is quicksort. However, the time complexity is O(nlogn). That is because quicksort do partition of whole array, and then recurisively do partition on the left and right subarray, but size of subarray is decrease in logn times, so total time complexity is O(logn). But if we only need to find the kth largest element, we don't need to do the participating for each subarray. We only need to do partition on the array we think it contains the kth largest element. Therefore, the time complexity is O(n), O(n/a),O(n/b)... (a,b is a constant), so the time complexity for whole array is O(n).

Visualization

3
startIndex
2
3
1
5
6
endIndex
4
p
k=2



So divide the array into two subarray, left subarray contains elements smaller than pivot, right subarray contains elements greater than pivot. And after division, put pivot back to the middle.

3
2
3
1
4
p
5
6
k=2



We can see that 4 is the 3rd largest element in the array, and we need to find 2nd largest, it is in the right subarray. So we only need to repeat the process, keep finding the 2nd largest element on the right subarray.

3
2
3
1
4
5
start
Index
6
end
Index
p
k=2






Processing:

3
2
3
1
4
5
6
p
k=2



And at this time 5 is the 2nd largest element in the right subarray, which is also the 2nd largest elements of whole array, so we can return 5 as the result.


Two situations:

If the problem is as the example, kth elements is in the right subarray, we find the kth element in right subarray, but if the kth elements is in the left subarray, assume pivot is the ath largest elements, we need to find the k-a th largest element in left subarray.
For the previous example, if k=5, process should be as follows:

3
2
3
1
p
4
5
6
k=2


1
p
2
3
3
4
5
6
k=2


1
2
3
p
3
4
5
6
k=2


At this time k is the 1st largest element, so find 2-1=1st largest element in left subarray, easily get final result 2.


Algorithm implementation:

                            
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int length = nums.length;
        int result = divide(nums,0,length-1,k);
        return result;
    }
    public int divide(int[]nums, int startIndex, int endIndex,int k){
        int random = (int) (Math.random() * (endIndex - startIndex + 1)) + startIndex;
        if(startIndex==endIndex){
            return nums[startIndex];
        }
        int arrLength=endIndex-startIndex+1;
        int x=nums[random];
        int temp=nums[random];
        nums[random]=nums[endIndex];
        nums[endIndex]=temp;

        int j=startIndex;
        int i=j-1;
        for(;jk){
            return divide(nums,i+2,endIndex,k);
        }
        return -1;
    }
}
Back

portfolio