Problem:
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.
Analysis:
This problem is great! It's a good time to make a good summary! We are always try to take advantage of a sorted array. 1. find duplicates 2. missing number ... However, for any kind of sorting alogrithm, as long as you want to get an array completely sorted. You have to to use at least O(logn) time for it. For some case you really don't need to get all elements sorted, since you may just want to find a qualified element meets certain characteristic. Quick sort is a weired algorithm compared with other other algorithm. Rather than take all other elements for each iteration, it finds the position of one element once a time. Then continue to find elements for other elements. The sub-algorthm of Quick sort is to find an element's rank in the array. (which could be acheive at O(n)). To make things more beautiful, the average time of using quick find kth element is actually O(n) time. The idea behind it is not hard, but it indeed take some minds to understand. Unit function: randomly pick an element (usually the first or last element of the valid range), find it is rank in the array. (please be noted the rank is start from 0) Basic idea: pick an element, we put all elements smaller than it before it, and put all elements larger than it after it. 1. To achieve this, we need to use two pointers, one starts from the low and the other starts from the end. int left = low; int right = high; 2. Once the left pointer finds out an element larger than the pivot, and the right pointer finds out the element smaller than the pivot. We exchange them! while (true) { while (right > left && nums[right] > pivot) right--; while (left < right && nums[left] <= pivot) left++; if (left == right) break; swap(nums, left, right); } Note: During the process of finding right elements to exchange, the left and right pointer may meet with each other. In this case, we should jump out the process of finding elements to exchange. 3. When the left and right pointer meets with each other. the meet up position is where we should put the pivot. int pivot = nums[low]; ... swap(nums, low, right); 4. iff the pivot's rank (index of meet up position) is just the rank we want to find. we return it. (The most beautiful part of quick select method is that, we never need to update on k!!!) if (cur_pos == k - 1) return pivot; //note pivot's ranke is in realtive with base 0 index. 5. iff the pivot's rank smaller than the rank we want to find, and are sure all elements before pivot actually with even smaller rank, we search the target at the part after pivot. if (cur_pos < k - 1) return findKth(nums, k, cur_pos+1, high); 6. iff the pivot's rank larger than the rank we ant to find, we search the target at the left part before pivot. if (cur_pos < k - 1) return findKth(nums, k, low, cur_pos-1); The idea is so powerful and beautiful, right? But there are some pitfalls in the implementation, you should be very careful!!! Mistake 1: Try to start from the element after the pivot (nums[low]). int pivot = nums[low]; ... int left = low+1; 1st concern: what if there are only one element left???? You may try to fix it through "if (low == hight) return nums[low]" Is that right? Nope!!! if the pivot's right index is low!!! the meet up position would not be it. (since we have left = low+1) Mistake 2: underestimate the order of moving two pointer: while (left < right && nums[left] <= pivot) left++; while (right > left && nums[right] > pivot) right--; The above code makes the same mistake in the mistake1. The logic if (nums[left] <= pivot) left++; Would skip the "low" index!!!If the real index for pivot is "low", we would get wrong answer. But if we put: while (right > left && nums[right] > pivot) right--; at the first. Since low is the smallest element in the range (it's real index is low), our right pointer would go straightly to meet it.
Solution:
public class Solution { public int findKthLargest(int[] nums, int k) { return findKth(nums, nums.length - k + 1, 0, nums.length - 1); } private int findKth(int[] nums, int k, int low, int high) { int pivot = nums[low]; int left = low; int right = high; while (true) { while (right > left && nums[right] > pivot) right--; while (left < right && nums[left] <= pivot) left++; if (left == right) break; swap(nums, left, right); } swap(nums, low, right); int cur_pos = right; if (cur_pos == k - 1) { return pivot; } else if (cur_pos < k - 1) { return findKth(nums, k, cur_pos+1, high); } else { return findKth(nums, k, low, cur_pos-1); } } private void swap(int[] nums, int low, int high) { int temp = nums[low]; nums[low] = nums[high]; nums[high] = temp; } }