Geek Answers Handbook

Find the largest number of Kth in one pass without saving the entire array

Algo, which I mean

  • save maxheap size K
  • insert each item
  • a smaller value occurs if the heap is full
  • In the end, Kth max is less than MaxHeap

This will give me O (NlogK). Is there a better algorithm? I cannot make a quick choice because the array cannot be stored in memory.

+5
source share
5 answers

Depending on the limitations of your memory, you can use a modified version of the median median algorithm to solve the problem in O (n) time and O (k) space.

. 2k . 2k , , k k . k . k , , k k . - k , , k - k . ( O (k) ) k- .

, O (n/k) O (k), O (n/k), , O ( k) , O (n). , , O (n + k) = O (n) . , - O (k), O (k), O (k) . , , .

, !

+11

, maxheap " ".

  • K -

  • , ,

    • .

  • - Kth.

O (N lg K) , K. .

0

- , .

public class nth {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        calc.getit(2);
    }

}
class calc{
    static int arr[] = { 1, 23, 47, 81, 92, 87, 52, 48, 56, 66, 65, 76, 71, 85,
        49, 53, 56, 61, 65, 84 };

    static void getit(int k){
        int i,j=0;
        for(i=0;i<arr.length;i++){
            int c=0;
            for(j=0;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    c++;
                }
            }
            if(c==k-1){
                System.out.println(arr[i]);
            }
        }
    }
}
0

PriorityQueue. :

import java.util.PriorityQueue;

public class FindKthLargestElementWithHeap {

    /**
     * We can use a min heap to solve this problem. 
     * The heap stores the top k elements.
     * Whenever the size is greater than k, delete the min.
     * Time complexity is O(nlog(k)).
     * Space complexity is O(k) for storing the top k numbers.
     */
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>(k);
        for(int i: nums){
            q.offer(i);

            if(q.size()>k){
                q.poll();
            }
        }

        return q.peek();
    }

    public static void main(String args[]) {
        int[] nums = {5,8,6,97,12,3,5,6,4,2,3,};
        //Return the second largest number
        System.out.println(findKthLargest(nums,2));
    }

}

: https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/FindKthLargestElementWithHeap.java.

0

More articles:


All Articles