Finding the largest K numbers in an unsorted array

Question

I am trying to find the largest K numbers given a sorted array.

ex: input - > [ 5, 12, 45, 32, 9, 20, 15] output -> K = 3, [45, 32, 20]

The code that I have written so far returns the largest K element, but it needs to return the largest K numbers. Any help would be appreciated.

public static int max_Numbers(int [] p, int K, int firstNum, int lastNum)
    {
        int pivot = partitionArr(p, firstNum, lastNum);
        int m = p.length - K;
        if (m == pivot)
        {
            return p[pivot];
        }
        if(m > pivot)
        {
            return max_Numbers(p, K, pivot + 1, lastNum);

        }
        else
        {
            return max_Numbers(p, K, firstNum, pivot - 1);
        }
    }

If efficiency isn't important just sort it and return to the top k — Mitch, Mar 17 '19 at 01:03
Read https://stackoverflow.com/questions/19227698/write-a-program-to-find-100-largest-numbers-out-of-an-array-of-1-billion-numbers. — Stephen C, Mar 17 '19 at 01:09
Also, note that your question could be closed as "Too broad" (since it is a "please help me" rather than a proper question) and "Off topic" (since it is apparently a request for debugging assistance without a proper MCVE) — Stephen C, Mar 17 '19 at 01:12
There is no `O(N)` solution. There is an `O(NlogK)` solution. Check that you have understood the problem. (Hint: if you substitute a specific value for `K`, that makes this a problem with an `O(N)` solution.) — Stephen C, Mar 17 '19 at 01:14
@stephenC: nowhere does it say the numbers need to be returned in order, although you may be right that it is somehow implicit. — rici, Mar 17 '19 at 01:20
@rici - The Question I linked to doesn't specify that the K elements should be delivered in order. I don't think I mentioned ordering ... — Stephen C, Mar 17 '19 at 01:31
@user11082882 - If you want a well-written explanation, read https://www.baeldung.com/java-kth-largest-element — Stephen C, Mar 17 '19 at 01:34
@stephenc: i didn't look at the question you linked to but an O(n) solution to the partitioning problem is [well-known](https://en.m.wikipedia.org/wiki/Median_of_medians). But it is only linear if you don't need the partition to be sorted (or, as you say, k is considered to be constant.) — rici, Mar 17 '19 at 01:40
(QuickSelect with median-of-medians partitioning is not efficient in practice. But it is guaranteed O(n).) — rici, Mar 17 '19 at 01:43
@msk: as described in the linked wikipedia article, you compute the median of medians, which gives you a guaranteed non-pathological pivot. You can compute the median of medians in O(n). — rici, Mar 17 '19 at 04:14
If the array is already sorted, you return the sub-array starting at index `N-K`. What am I missing? — selbie, Mar 17 '19 at 04:38

score 0 · Answer 1 · answered Mar 17 '19 at 04:28

0

Using your sorted array,

for(int i=array.length-1; i>=0 && array.length-1 - i < K; i--) System.out.println(array[i]));

answered Mar 17 '19 at 04:28

FailingCoder

757
1
8
20

score 0 · Answer 2 · answered Mar 17 '19 at 08:03

One property of the pivot and partition you are using is that after every partition step, it is guaranteed that all elements before the pivot happen to be smaller or equal than the pivot, and everything after the pivot is larger. Thus, after you find the pivot that is the K-th, the array will have the K largest after it.

Finding the largest K numbers in an unsorted array

2 Answers2