LeetCode - Algorithms - 215. Kth Largest Element in an Array

It seemed that every leetcode algorithms problem has mulple solutions, so do this one. I just verified solutions of other peer.

Java

Quickselect

© Quickselect: Kth Greatest Value

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 {
	private void exch(int[] a, int i, int j) {
		int swap = a[i];
		a[i] = a[j];
		a[j] = swap;
	}
    
	private int partition(int[] a, int lo, int hi) {
		int pivot = lo + new Random().nextInt(hi - lo + 1);
		exch(a, hi, pivot);
		for (int i = lo; i < hi; i++) {
			if (a[i] > a[hi]) {
				exch(a, i, lo);
				lo++;
			}
		}
		exch(a, lo, hi);
		return lo;
	}
    
	private int quickselect(int[] a, int left, int right, int k) {
		if (left <= right) {
			int pivot = partition(a, left, right);
			if (pivot == k) {
				return a[k];
			}
			if (pivot > k) {
				return quickselect(a, left, pivot - 1, k);
			}
			return quickselect(a, pivot + 1, right, k);
		}
		return Integer.MIN_VALUE;
	}    
    
    public int findKthLargest(int[] nums, int k) {
        return quickselect(nums, 0, nums.length - 1, k - 1);
    }
}

Submission Detail

  • 32 / 32 test cases passed.
  • Runtime: 1 ms, faster than 98.04% of Java online submissions for Kth Largest Element in an Array.
  • Memory Usage: 39.3 MB, less than 11.22% of Java online submissions for Kth Largest Element in an Array.

Solution 1: sorting

1
2
3
4
5
6
7
8
import java.util.Arrays;

class Solution {
    public int findKthLargest(int[] nums, int k) {
		Arrays.sort(nums);
		return nums[nums.length - k];        
    }
}

Submission Detail

  • 32 / 32 test cases passed.
  • Runtime: 3 ms, faster than 84.58% of Java online submissions for Kth Largest Element in an Array.
  • Memory Usage: 35.7 MB, less than 98.57% of Java online submissions for Kth Largest Element in an Array.

Solution 2: min heap

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
    	PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(k);
    	for(int i : nums) {
    		minHeap.offer(i);
    		if (minHeap.size()>k)
    			minHeap.poll();
    	}
    	return minHeap.peek();       
    }
}

Submission Detail

  • 32 / 32 test cases passed.
  • Runtime: 8 ms, faster than 51.68% of Java online submissions for Kth Largest Element in an Array.
  • Memory Usage: 35.7 MB, less than 98.37% of Java online submissions for Kth Largest Element in an Array.

Solution 3: a similar method like 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
class Solution {
    public int findKthLargest(int[] nums, int k) {
		if (k < 1 || nums == null) {
			return 0;
		}
		return getKth(nums.length - k + 1, nums, 0, nums.length - 1);       
    }

	private int getKth(int k, int[] nums, int start, int end) {
		int pivot = nums[end];
		int left = start;
		int right = end;
		while (true) {
			while (nums[left] < pivot && left < right) {
				left++;
			}
			while (nums[right] >= pivot && right > left) {
				right--;
			}
			if (left == right) {
				break;
			}
			swap(nums, left, right);
		}
		swap(nums, left, end);
		if (k == left + 1) {
			return pivot;
		} else if (k < left + 1) {
			return getKth(k, nums, start, left - 1);
		} else {
			return getKth(k, nums, left + 1, end);
		}
	}

	private void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

Submission Detail

  • 32 / 32 test cases passed.
  • Runtime: 22 ms, faster than 37.24% of Java online submissions for Kth Largest Element in an Array.
  • Memory Usage: 37.5 MB, less than 94.43% of Java online submissions for Kth Largest Element in an Array.