Java:使用2个数组查找数组的第K个最大元素 [英] Java: Find the Kth largest element of an array, using 2 arrays

问题描述

以下是有关算法/解决方案的说明:

Here is the description about the algorithm/solution:

• 输入:一个整数数组和一个数组索引
• 输出:数组的第K个最大元素
• 将前K个元素读入辅助数组(到目前为止，找到的K个最大元素)
• 排序K元素数组

• 然后:

• 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];
}

例如:

代码应根据以下信息返回值:8.

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?

推荐答案

您需要解决以下问题:

1. 在 Arrays.copyOfRange(array，from，to)方法中， to 索引是唯一的.因此，您需要像 Arrays.copyOfRange(bigArray，0，k)这样，以便将第一个 k 元素复制到辅助数组.
2. 您遍历主数组中其余数组元素并更新辅助数组的逻辑是错误的.

1. 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.
2. The logic where you loop over the remaining array elements from the main array and update the auxiliary array is wrong.

例如，让辅助数组为: [4，6] ，下一个主数组元素为 2 .根据您的逻辑，辅助数组将更新为 [6，6] ，因为您首先将索引为 1 的元素复制到索引为 0 的辅助数组，然后检查新元素(来自主数组)是否大于辅助数组中索引为 1 的元素.在这种情况下，新元素较小，因此仅发生复制，并且我们的辅助数组已损坏.

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];
}

这篇关于Java:使用2个数组查找数组的第K个最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！