解决这个问题的另一种方法是使用Quickselect。这应该得到 O（n） 的总平均时间复杂度。请考虑以下情况：

1. 使用快速选择 （O（n） 查找第 k个最大数字 x)
2. 再次循环访问数组（或仅通过右侧分区）（O（n））并将所有元素保存在 x ≥
3. 返回已保存的元素

（如果存在重复的元素，则可以通过计算需要添加到结果中的 x 重复项数来避免这些元素。

您的问题与您链接到的SO问题中的问题之间的区别在于，您只有一百万个元素，因此它们绝对可以保留在内存中以允许正常使用Quickselect。

有一个由一百万个整数组成的大型未排序数组。用户想要检索最大的元素。K

在此期间，我强烈暗示我需要对数组进行排序。

因此，我建议使用内置或自定义实现sort()

我想这并不是一个真正的暗示，而是一种欺骗你的把戏（测试你的知识有多强）。

如果选择通过使用内置的 Dual-Pivot 快速排序对整个源数组进行排序来解决问题，则无法获得比 O（n log n） 更好的时间复杂度。

相反，我们可以维护一个PriorytyQueue来存储结果。在迭代每个元素的源数组时，我们需要检查队列是否已达到大小，如果不是元素应添加到队列中，否则（大小等于）我们需要将下一个元素与队列中的最低元素进行比较 - 如果下一个元素较小或相等，则应忽略它，如果它更大，则必须删除最低元素，并且需要添加新元素。KK

这种方法的时间复杂度为 O（n log k），因为将新元素添加到 size 中会花费 O（k），在最坏的情况下，此操作可以执行几次（因为我们正在迭代 size 数组）。PriorytyQueueknn

请注意，最佳情况的时间复杂度为Ω（n），即线性。

因此，排序和使用a在大O方面的差异归结为O（n log n）和O（n log k）之间的差异。当比这种方法小得多时，将带来显著的性能提升。PriorytyQueuekn

下面是一个实现：

public static int[] getHighestK(int[] arr, int k) {
    Queue<Integer> queue = new PriorityQueue<>();
    
    for (int next: arr) {
        if (queue.size() == k && queue.peek() < next) queue.remove();
        if (queue.size() < k) queue.add(next);
    }
    
    return toIntArray(queue);
}

public static int[] toIntArray(Collection<Integer> source) {
    return source.stream().mapToInt(Integer::intValue).toArray();
}

main()

public static void main(String[] args) {
    System.out.println(Arrays.toString(getHighestK(new int[]{3, -1, 3, 12, 7, 8, -5, 9, 27}, 3)));
}

输出：

[9, 12, 27]

在 O（n） 中排序

当给定数组的内容存在一些约束时，我们可以实现O（n）的最坏情况时间复杂度。假设它只包含范围内的数字（当然，你没有被告知，但在面试期间澄清问题要求总是好的）。[-1000,1000]

在这种情况下，我们可以使用具有线性时间复杂性的计数排序。或者更好的是，只需构建一个直方图（计数排序的第一步）并查看最高值的存储桶，直到您看到 K 个计数。（即，实际上不要扩展回完全排序的数组，只需将计数扩展回顶部的K排序元素。仅当计数数组（可能的输入值）小于输入数组的大小时，创建直方图才有效。

另一种可能性是当给定的数组部分排序时，由几个排序的块组成。在这种情况下，我们可以使用Timsort，它擅长查找排序的运行。它将在线性时间内处理它们。

Timsort已经在Java中实现了，它用于对对象进行排序（而不是基元）。因此，我们可以利用经过良好优化和全面测试的实现，而不是编写我们自己的实现，这很棒。但是由于我们被赋予了一个基元数组，因此使用内置的Timsort将产生额外的成本 - 我们需要将数组的内容复制到包装器类型的列表（或数组）中。