Sort, Heap, BinarySearch, QuickSelect, Counting


  • 1
    H

    Tried different methods with Java, here's the run time:
    // method 1: tuned sort, 6ms
    // method 2: Heap/PriorityQueue, 12ms
    // method 3: binarySearch, 5ms
    // method 4: quick-select, 3ms, 4ms(3-way)
    // method 5: with counting, 3ms

        // method 1: tuned sort, 6ms
        // time: O(nlgn) + mem: O(1)
        public int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length-k];
        }
    
        // method 2: Heap/PriorityQueue, 12ms
        // time: O(nlgk) + mem: O(k)
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> q = new PriorityQueue();
            for (int i : nums) {
                q.offer(i);
                if (q.size() > k) {
                    q.poll();
                }
            }
            return q.peek();
        }
    
        // method 3: binarySearch, 5ms
        // time: O(n + n*lg(2^32-1)) + mem: O(1)
        public int findKthLargest(int[] nums, int k) {
            int max = nums[0];
            int min = nums[0];
            for (int i : nums) {
                max = Math.max(max, i);
                min = Math.min(min, i);
            }
            // binary search
            while (min < max) {
                int med = min + (max - min)/2;
                int cnt = countLarger(nums, med);
                if (cnt > k-1) {
                    min = med + 1;
                } else {
                    max = med;
                }
            }
            return min;
        }
        
        public int countLarger(int[] nums, int med) {
            int res = 0;
            for (int i : nums) {
                res += i > med ? 1 : 0;
            }
            return res;
        }
    
        // method 4: quick-select, 3ms, 4ms(3-way)
        // time: O(n) + mem: O(1) + recursive function call
        public int findKthLargest(int[] nums, int k) {
            // possible with shuffle to make sure randomness of nums
            return partition(nums, 0, nums.length-1, k);
        }
        // 3ms
        public int partition2(int[] nums, int lo, int hi, int k) {
            // 2-way partition
            int l = lo + 1;
            int r = hi;
            // choose medium as pivot for small array
            swap(nums, lo, (hi+lo)/2);
            // start partition
            while (l <= r) {
                if (nums[l] >= nums[lo]) {
                    l++;
                } else {
                    swap(nums, l, r);
                    r--;
                }
            }
            if (k == r - lo + 1) return nums[lo];
            if (k <= r - lo) return partition2(nums, lo+1, r, k);
            else return partition2(nums, l, hi, k - (l-lo));
        }
        // 4ms
        public int partition(int[] nums, int lo, int hi, int k) {
            // 3-way partition (good when there are a lot of duplicates)
            int lt = lo;
            int gt = hi;
            // choose medium as pivot (possible with shuffle)
            swap(nums, lo, (lo+hi)/2);
            // start partition
            int i = lt + 1;
            while (i <= gt) {
                if (nums[i] > nums[lt]) { //larger number on the left
                    swap(nums, i, lt);
                    lt++;
                    i++;
                } else if (nums[i] < nums[lt]) {
                    swap(nums, i, gt);
                    gt--;
                } else {
                    i++;
                }
            }
            if (k > lt - lo && k <= gt + 1 - lo) return nums[lt];
            if (k <= lt - lo) return partition(nums, lo, lt-1, k);
            else return partition(nums, gt+1, hi, k - (gt+1-lo)); //if (k > gt+1-lo)
        }
        
        public void swap(int[] nums, int a, int b) {
            int tmp = nums[a];
            nums[a] = nums[b];
            nums[b] = tmp;
        }
    
        // method 5: with counting, 3ms
        // if data range is relatively small (compare to n)
        public int findKthLargest(int[] nums, int k) {
    		int max = nums[0];
    		int min = nums[0];
    		// find max and min: O(n)
    		for (int i = 1; i < nums.length; i++){
    			max = Math.max(max, nums[i]);
    			min = Math.min(min, nums[i]);
    		}
    		// count occurence: O(n)
    		int[] count = new int[max-min+1];
    		for (int i = 0; i < nums.length; i++){
    			count[nums[i]-min]++;
    		}
    		// find kth largest element
    		for (int i = count.length-1; i >= 0; i--){
    			k -= count[i];
    			if (k <= 0) { return i + min; }
    		}
    		return 0;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.