-1

I am having some problems with a sorting problem.

The statement:

Write a method KthLargest() that, given an array containing integers in some arbitrary order and an integer k, returns the k-th largest element in the array. Assuming that k is a small number and n is a very large number, your algorithm should be as fast as possible in terms of the worst-case number of comparisons, so do not sort the entire array of size n to find out the k-th largest element. You may use the Arrays.sort() method provided in the Java library.

I have clear ideas on how to do this problem... That is if I can sort the entire array first.

public static int KthLargest(int[] inputArray, int k)
{
    Arrays.sort(inputArray);
    return inputArray[k];
}

However, the problem statement specifically states that I must not sort the entire array.

theGreenCabbage
  • 5,197
  • 19
  • 79
  • 169

2 Answers2

1

Use a k sized min-heap to find the kth largest/smallest element. You need not sort the elements to do this . I can write further, but this seems to be a homework question.

A heap is a DS where largest/smallest element is at the top . If largest element it as top it is max heap , else it is min heap. They are also called priority queues. PS: I do mean a k sized min heap

Biswajit_86
  • 3,661
  • 2
  • 22
  • 36
  • Could you go deeper into what a k-sized min-heap is? This appears to be an algorithm you are talking about, which I've never learned before. – theGreenCabbage May 07 '14 at 01:03
  • Once you understand the heap algorithm, you can also understand the link provided by @blorgbeard for the kth largest element in a partition – Biswajit_86 May 07 '14 at 01:05
  • I used the quick select algorithm to achieve this: http://en.wikipedia.org/wiki/Quickselect – theGreenCabbage May 07 '14 at 01:56
1

You can use the binary search algorithm. It is very good to quickly sort tons of stuff. Basically, it checks if the k is larger or smaller than the middle value, then it cut the array in half and then it loop. If you did not sort before using the binary search, it will fail.

Pseudocode :

Binary search (algorithm)

I = 1

DO
 M = (I + J) / 2
 IF K > ARRAY[M] THEN I = M + 1 / / upper half
 ELSE J = M - 1 / / lower half
WHILE (TABLE[M] != K OR I < J)

IF TABLE[M] = K THEN RETURN M
ELSE RETURN -1 //-1 = not found

Java code :

static void Search(int[] inputArray, int k) {  
    int Found = -1;
    int comp = 0;
    int Mid = 0;
    int f = inputArray.length;
    int d = inputArray.length%2;

    while (Found == -1 || d < f){
        Mid = (d + f)/2;

        NomComp = k.compareToIgnoreCase(inputArray[Mid]);

        if (NomComp == 0) {
            Found = k;
        } else if (NomComp > 0) {
            d = Mid + 1;  
        } else {
            f = Mid - 1;
        }
    }

    return Found;

}
Alipharo
  • 11
  • 3