Java: Find the Kth largest element of an array, using 2 arrays

Question

Here is the description about the algorithm/solution:

Input: An array of ints and an array index
Output: Kth largest element of the array
Read the first K elements into an auxiliary array (the K largest found so far)
Sort the K-element array

Then:

 for each remaining element {
    if (if it is smaller than the smallest element of the aux. array) {
        throw it away
    } else { 
        remove the current smallest element of the auxiliary array
        place the element into the correct position in the auxiliary array
    }
 }

 then return the smallest (the Kth) element of the auxiliary array

I have come up with the following solution:

public int findElement() throws IndexingError {
    int[] bigArray = getArray();
    int k = getIndex();
    if (k <= 0 || k > bigArray.length) {
        throw new IndexingError();
    }

    int[] smallArray = Arrays.copyOfRange(bigArray,0,k-1);
    Arrays.sort(smallArray);


    for (int i = k; i < bigArray.length; i++) {
        for (int ii = 1; ii < smallArray.length; ii++) {
            smallArray[ii-1] = smallArray[ii];
            if (bigArray[i] > smallArray[ii]) {
                smallArray[ii] = bigArray[i];
                System.out.println(smallArray[ii] + " " + smallArray[ii-1] + " " + bigArray[i]);
                break;

            }
        }

    }

    return smallArray[0];
}

So for example:

The code should return the value of: 8, based on the info below:

array = [2, 3, 8, 7, 1, 6, 5, 9, 4, 0]
k = 2

Running the above code yields different outputs every time, if you run it enough times you get the correct answer?

Could someone identify/fix flaws in my code?

I agree with VIPER, you could simply sort the array and get the Kth element. — Muizz Mahdy
– Muizz Mahdy, Commented Oct 7, 2018 at 16:12
Yes, I know what the obvious solution is however I have been asked to do it this way specifically — Usaamah Patel
– Usaamah Patel, Commented Oct 7, 2018 at 16:14
Even you are restricted to use a second array, you have to place k elements in it in a sorted fashion. So you can just use any sorting algorithm but change it a bit to place elements in the second array and restrict it to k elements. For instance with bubble sort find only first k elements and place ones or element indexes into the second array — Maxim
– Maxim, Commented Oct 7, 2018 at 16:17

Apoorv Agarwal · Accepted Answer · 2018-10-07 19:21:11Z

0

You need to fix the following issues:

In Arrays.copyOfRange(array, from, to) method the to index is exclusive. So, you need to have it like Arrays.copyOfRange(bigArray,0,k) in order to copy first k elements to the auxiliary array.
The logic where you loop over the remaining array elements from the main array and update the auxiliary array is wrong.

For example, let auxiliary array be: [4, 6], and the next main array element be 2. According to your logic the auxiliary array will be updated to [6, 6] since you first copy the element at index 1 to index 0 in the auxiliary array and then check if the new element(from main array) is greater than the element at index 1 in the auxiliary array. In this case the new element is smaller, so just the copying takes place, and we get corrupted auxiliary array.

What you simply need to do is, for every new element from the main array, check if it's greater than the first element in the auxiliary array. If it is, then this new element should be a part of the auxiliary array and should be placed at the proper position. You can use the bubble sort technique to find the proper place.

public int findElement() throws IndexingError {
    int[] bigArray = getArray();
    int k = getIndex();
    if (k <= 0 || k > bigArray.length) {
        throw new IndexingError();
    }

    int[] smallArray = Arrays.copyOfRange(bigArray,0,k);
    Arrays.sort(smallArray);


    for (int i = k; i < bigArray.length; i++) {
        if(bigArray[i] > smallArray[0]) {
            smallArray[0] = bigArray[i];
            int j = 0;
            while((j < k-1) && (smallArray[j] > smallArray[j+1])) {
                swap(smallArray[j], smallArray[j+1]);
                j++;
            }
        }

    }

    return smallArray[0];
}

edited Oct 7, 2018 at 19:21

answered Oct 7, 2018 at 16:38

Apoorv Agarwal

3361 silver badge7 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Usaamah Patel Over a year ago

Where would I implement the bubble sort? Within the while loop?

Apoorv Agarwal Over a year ago

I have already implemented it(technique similar to bubble sort) in the above code snippet.

Usaamah Patel Over a year ago

Ah ok, so I assume the swap() puts the value from smallArray[j+1] into smallArray[j]?

Apoorv Agarwal Over a year ago

It swaps the values, puts the original value of smallArray[j] into smallArray[j+1] and puts the original value of smallArray[j+1] in smallArray[j]

Apoorv Agarwal Over a year ago

int temp = smallArray[j]; smallArray[j] = smallArray[j+1]; smallArray[j+1] = temp; This is swap implementation which you can use.

|

Collectives™ on Stack Overflow

Java: Find the Kth largest element of an array, using 2 arrays

1 Answer 1

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related