LeetCode 215 - Kth Largest Element in an Array


LeetCode 215 - Kth Largest Element in an Array - 我的博客 - ITeye技术网站
Find the kth largest element in an unsorted array.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Time complexity: http://stackoverflow.com/questions/5945193/average-runtime-of-quickselect
First Step: T(n) = cn + T(n/2)

c(n + n/2 + n/4 + ... + 2 + 1) = c(2n) //sum of a GP
Hence, it's O(n)
  1. public int findKthLargest(int[] nums, int k) {  
  2.     return findKthLargest(nums, 0, nums.length-1, k-1);  
  3. }  
  4.   
  5. private int findKthLargest(int[] nums, int l, int h, int k) {  
  6.     if(k<l || k>h) return -1;  
  7.     int p = partition(nums, l, h);  
  8.     if(p == k) {  
  9.         return nums[p];  
  10.     } else if(p > k) {  
  11.         return findKthLargest(nums, l, p-1, k);  
  12.     } else {  
  13.         return findKthLargest(nums, p+1, h, k);  
  14.     }  
  15. }  
  16.   
  17. private int partition(int[] nums, int l, int h) { 
  18.     int pivot = nums[h];  
  19.     int p = l;  
  20.     for(int i=l; i<h; i++) {  
  21.         if(nums[i]>pivot) {  
  22.             swap(nums, i, p++);  
  23.         }  
  24.     }  
  25.     swap(nums, p, h);  
  26.     return p;  
  27. }  
  28.   
  29. private void swap(int[] nums, int i, int j) {  
  30.     int tmp = nums[i];  
  31.     nums[i] = nums[j];  
  32.     nums[j] = tmp;  
  33. }
https://leetcode.com/problems/kth-largest-element-in-an-array/discuss/60294/Solution-explained


  • 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).

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.

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.
http://www.jiuzhang.com/solutions/kth-largest-element/
    public int kthLargestElement(int k, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (k <= 0) {
            return 0;
        }
        return helper(nums, 0, nums.length - 1, nums.length - k + 1);
        
    }
    public int helper(int[] nums, int l, int r, int k) {
        if (l == r) {
            return nums[l];
        }
        int position = partition(nums, l, r);
        if (position + 1 == k) {
            return nums[position];
        } else if (position + 1 < k) {
            return helper(nums, position + 1, r, k);
        }  else {
            return helper(nums, l, position - 1, k);
        }
    }
    public int partition(int[] nums, int l, int r) {
        // 初始化左右指针和pivot
        int left = l, right = r;
        int pivot = nums[left];
        
        // 进行partition
        while (left < right) {
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            nums[right] = nums[left];
        }
        
        // 返还pivot点到数组里面
        nums[left] = pivot;
        return left;//return where is the pivot; its position         
    }
https://segmentfault.com/a/1190000003704825
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k - 1, 0, nums.length - 1);
    }
    
    private int quickSelect(int[] arr, int k, int left, int right){
        int pivot = arr[(left + right) / 2];
        int orgL = left, orgR = right;
        while(left <= right){
            // 从右向左找到第一个小于枢纽值的数
            while(arr[left] > pivot){
                left ++;
            }
            // 从左向右找到第一个大于枢纽值的数
            while(arr[right] < pivot){
                right --;
            }
            // 将两个数互换
            if(left <= right){
                swap(arr, left, right);
                left ++;
                right --;
            }
        }
        // 最后退出的情况应该是右指针在左指针左边一格
        // 这时如果右指针还大于等于k,说明kth在左半边
        if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);
        // 这时如果左指针还小于等于k,说明kth在右半边
        if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
        return arr[k];
    
    }
A quick-selection algorithm:
The quick selection algorithm is very similar to quick sort. Instead of sorting, it only needs the partition step, where it finds the pivot and compare the pivot with k. 
Since it only uses the partition algorithm, the average time complexity is O(n). However, the worst case complexity is O(n^2). 

In which case the quick selection has time complexity of O(n^2)?
Let's say you have a sorted array, 1 2 3 4 5, and k = 1, means we select the largest element which is 5. For each element in the array, we need to run the partition algorithm and discard the pivot only, which has the time complexity of O(n). For the n elements in the array, the overall time complexity is O(n^2). Therefore, for either quick sort and quick select algorithm, we usually need to well suffle the array for the reason each time the pivot is chosen in the half.
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         
        return findKthLargestHelper(nums, 0, nums.length - 1, nums.length - k);
    }
     
    private int findKthLargestHelper(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return nums[lo];
        }
         
        int pivot = partition(nums, lo, hi);
        if (pivot == k) {
            return nums[k];
        }
         
        if (pivot > k) {
            return findKthLargestHelper(nums, lo, pivot - 1, k);
        } else {
            return findKthLargestHelper(nums, pivot + 1, hi, k);
        }
    }
     
    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        int i = lo + 1;
        int j = hi;
         
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
             
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
             
            if (i <= j) {
                swap(nums, i, j);
            }
        }
         
        swap(nums, lo, j);
         
        return j;
    }
     
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
https://leetcode.com/discuss/36966/solution-explained
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.
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); } }
X. Iterative Version
https://leetcode.com/discuss/36991/java-quick-select
http://www.cnblogs.com/yrbbest/p/4982861.html
Discard half each time: n+(n/2)+(n/4)..1 = n + (n-1) = O(2n-1) = O(n), because n/2+n/4+n/8+..1=n-1.
public int findKthLargest(int[] nums, int k) { int start = 0, end = nums.length - 1, index = nums.length - k; while (start < end) { int pivot = partion(nums, start, end); if (pivot < index) start = pivot + 1; else if (pivot > index) end = pivot - 1; else return nums[pivot]; } return nums[start]; } private int partion(int[] nums, int start, int end) { int pivot = start, temp; while (start <= end) { while (start <= end && nums[start] <= nums[pivot]) start++; while (start <= end && nums[end] > nums[pivot]) end--; if (start > end) break; temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; } temp = nums[end]; nums[end] = nums[pivot]; nums[pivot] = temp; return end; }

public class Solution {
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
        return;
    }
    
    private int partition(
        int[] nums, 
        int low, 
        int high, 
        int pivotIdx
    ) {
        int pivotVal = nums[pivotIdx];
        swap(nums, pivotIdx, high);
        int storeIdx = low;
        for (int i = low; i < high; i++) {
            if (nums[i] > pivotVal) {
                swap(nums, storeIdx, i);
                storeIdx++;
            }
        }
        swap(nums, storeIdx, high);
        return storeIdx;
    }
    
    private int findKthLargest(
        int[] nums, 
        int low, 
        int high, 
        int k
    ) {
        if (low == high) {
            return nums[low];
        }
        while (true) {
            int offset = new java.util.Random().nextInt(
                             high - low + 1
                         );
            int pivotIdx = low + offset;
            pivotIdx = partition(nums, low, high, pivotIdx);
            if (pivotIdx == k) {
                return nums[k];
            }
            if (pivotIdx > k) {
                high = pivotIdx - 1;
            } else {
                low = pivotIdx + 1;
            }            
        }
    }
    
    public int findKthLargest(int[] nums, int k) {
        return findKthLargest(nums, 0, nums.length - 1, k - 1);
    }
X. Shuffle
改进了一下quick-select, 在查找前按照塞神的建议先进行了O(n)的shuffle,速度果然快了不少, 从47ms到达了7ms 
https://discuss.leetcode.com/topic/14597/solution-explained
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);
        }
    }
https://segmentfault.com/a/1190000003704825
时间 O(NlogK) 空间 O(K)
思路
遍历数组时将数字加入优先队列(堆),一旦堆的大小大于k就将堆顶元素去除,确保堆的大小为k。遍历完后堆顶就是返回值。
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> p = new PriorityQueue<Integer>();
        for(int i = 0 ; i < nums.length; i++){
            p.add(nums[i]);
            if(p.size()>k) p.poll();
        }
        return p.poll();
    }
A max-heap solution:
First of all, put all elements into the heap. Then poll the top k elements from the max heap then we get the result. The time complexity for max heap is  O(n) + O(k * logn). The space complexity is O(n).
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(nums.length, Collections.reverseOrder());
         
        for (int num : nums) {
            maxHeap.offer(num);
        }
         
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.poll();
        }
         
        return result;
    }

X. 
  • 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.

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();
}

A min-heap solution:
 -- Step 1: put the first k elements into the heap. Time complexity is O(k). 
 -- Step 2: Start from elements k + 1 to n, compare each one with heap.peek(). If greater than the peek, replace with the element. The time complexity is O((n - k) logk).
  -- Step 3: After we iterate the array, the heap stores the top k elements, and the kth largest element is the minimum element of the heap, which is peek.

The space complexity is O(k). 
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k);
         
        for (int num : nums) {
            if (maxHeap.size() < k) {
                maxHeap.offer(num);
            } else {
                if (num > maxHeap.peek()) {
                    maxHeap.poll();
                    maxHeap.offer(num);
                }
            }
        }
         
        return maxHeap.peek();
    }

    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(nums.length, Collections.reverseOrder());
         
        for (int num : nums) {
            maxHeap.offer(num);
        }
         
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = maxHeap.poll();
        }
         
        return result;
    }
时间 O(NlogN) 空间 O(1)
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
Note that it is the kth largest element in the sorted order, not the kth distinct element.
X. Random partition
http://analgorithmaday.blogspot.com/2011/05/random-partition-its-use-cases.html
int random_partition(int* arr, int size)
{
    srand(time(NULL));
    int pivotIdx = rand() % size;
    int pivot = arr[pivotIdx];
    int i=-1;
    int j=0;
    swap(arr[pivotIdx], arr[size-1]); // move pivot element to the end
    pivotIdx = size-1;
 
    while(j < size)
    {
        if(arr[j] <= pivot)
        {
            i = i+1;
            swap(arr[i], arr[j]);
        }
        j++;
    }
 
    swap(arr[i+1], arr[pivotIdx]);
    return i+1;
}
http://www.sanfoundry.com/java-program-implement-quick-sort-randomization/
  1.     public static void QuickSort(int left, int right) 
  2.     {
  3.         if (right - left <= 0)
  4.             return;
  5.         else 
  6.         {
  7.             Random rand = new Random();
  8.             int pivotIndex = left + rand.nextInt(right - left + 1);
  9.             swap(pivotIndex, right);
  10.  
  11.             int pivot = sequence[right];
  12.             int partition = partitionIt(left, right, pivot);
  13.             QuickSort(left, partition - 1);
  14.             QuickSort(partition + 1, right);
  15.         }
  16.     }
  17.  
  18.     public static int partitionIt(int left, int right, long pivot) 
  19.     {
  20.         int leftPtr = left - 1;
  21.         int rightPtr = right;
  22.         while (true) 
  23.         {
  24.             while (sequence[++leftPtr] < pivot)
  25.                 ;
  26.             while (rightPtr > 0 && sequence[--rightPtr] > pivot)
  27.                 ;
  28.  
  29.             if (leftPtr >= rightPtr)
  30.                 break;
  31.             else
  32.                 swap(leftPtr, rightPtr);
  33.         }
  34.         swap(leftPtr, right);
  35.         return leftPtr;
  36.     }
Read full article from LeetCode 215 - Kth Largest Element in an Array - 我的博客 - ITeye技术网站

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts