从数组中返回K个最大的元素。(JAVA)

Question

public static Word[] simpleSelect(Word[] array, int k){
    k= array.length;
    for(int i = 0; i< k-1; i++){
        for(int j = 0; j<k-i-1; j++){
            if(array[j].compareTo(array[j+1]) < 0){
                swap(array,j, j+1); 
            }
        }           
    }
    return array;
}

我创建上述代码是为了通过冒泡排序从数组中返回K最大的元素。我想让这个方法成为O(nk)。我已经编写了这段代码，并计算出返回的数组不打印具有k大小的数组。相反，它只是打印相同长度的原始数组，只是冒泡排序。

例如，如果我的原始数组是{1,19, 7 ,26 ,9 ,85}，而我的k值是2，我希望它返回{85,26}。取而代之的是，无论k值是什么，当前此代码都返回{85,26,19,9,7,1}。

我想知道我在这里做错了什么，也想知道我在O(nk)时间内编码是否正确。

Answer 1

1. k在第2行被重新赋值：k = array.length;这就是为什么无论k.
2. As的值是多少，方法都会运行的原因bubble sort的平均复杂度为O(n^2)，它必须进行调整以满足您的O(nk)要求。

Answer 2

假设我们有以下数字数组

static int[] arr = {456, 12 , 998, 546, 12,  987, 6456, 66, 9789};

我们将通过迭代找到数组中的最大数组，然后标记该数组中的最大数，从而构建包含k个最大数组的数组，这样它就不会再次被挑选。

这是找到k个最大元素的方法：

private static int[] kLargest(int[] arr, int k){
    int[] klargest = new int[k];
    for(int i=0;i<k;i++){
        klargest[i] = findAndMarkLargest(arr);
    }
    return klargest;
}

这是找到单个最大的元素，然后标记它的方法(通过将元素设置为Integer.MIN_VALUE)

private static int findAndMarkLargest(int[] arr){
    int largest = Integer.MIN_VALUE;
    for(int i=0;i<arr.length;i++){
        if(arr[i] > largest){
            largest = arr[i];
        }
    }
    for(int i=0;i<arr.length;i++){
        if(arr[i] == largest){
            arr[i] = Integer.MIN_VALUE;
        }
    }
    return largest;
}

main方法(简单地调用kLargest方法)如下所示：

public static void main (String[] args) throws java.lang.Exception
{
    // your code goes here
    System.out.println(Arrays.toString(kLargest(arr, 3)));
}

和输出：

9789、6456、998

每次调用findAndMarkLargest都需要2*n次操作(因为它在数组上运行了两次)。

方法findAndMarkLargest被“kLargest”调用了k次。因此，就大O符号而言，这是O(2kn)，它等同于O(nk)