Tan*_*ean 33 java arrays sorting algorithm data-structures
我最近在面试期间进行了编码测试。有人告诉我：
有一个一百万个的大型未排序数组
int。用户想要检索K最大的元素。你会实现什么算法？
在此期间，我强烈暗示我需要对数组进行排序。
因此，如果性能确实很重要，我建议使用内置sort()或自定义实现。然后我被告知，使用Collectionor数组来存储k最大的元素和 for 循环可以实现大约O(N)，事后看来，我认为这是O(N*k)因为每次迭代都需要与大小数组进行比较K以找到要替换的最小元素，而需要对数组进行排序将导致代码至少为O(N log N).
然后我回顾了 SO 上的这个链接，它建议K数字的优先级队列，每次找到较大的元素时删除最小的数字，这也会给出O(N log N). 编写一个程序，从 10 亿个数字的数组中找出 100 个最大的数字
for循环方法不好吗？我应该如何证明使用 for 循环或优先级队列/排序方法的优点/缺点？我认为，如果数组已经排序，则不需要再次迭代整个数组，即如果对排序数组调用其他检索方法，则它应该是恒定时间。运行实际代码时是否存在一些我在理论化伪代码时没有考虑到的性能因素？
Ber*_*hur 24
解决此问题的另一种方法是使用Quickselect。这将为您提供O(n)的总平均时间复杂度。考虑一下：
\n（如果存在重复的元素，您可以通过计算需要添加到结果中的x重复项的数量来避免它们。）
\n您的问题与您链接到的SO问题中的问题之间的区别在于您只有一百万个元素，因此它们绝对可以保留在内存中以允许正常使用Quickselect。
\nAle*_*nko 11
\n\n有一个包含一百万个整数的大型未排序数组。用户想要检索
\nK最大的元素。在此期间，我强烈暗示我需要对数组进行排序。
\n因此，我建议使用内置
\nsort()或自定义\n实现
我想这并不是真正的暗示，而是一种欺骗你的伎俩（测试你的知识有多强）。
\n如果您选择通过使用内置的Dual-Pivot Quicksort对整个源数组进行排序来解决该问题，则无法获得比O(n log n)更好的时间复杂度。
\n相反，我们可以维护一个PriorityQueue来存储结果的。在迭代每个元素的源数组时，我们需要检查队列是否已达到 size K，如果没有，则应将元素添加到队列中，否则（大小等于K）我们需要将下一个元素与最低元素进行比较队列中的元素 - 如果下一个元素小于或等于，我们应该忽略它，如果它大于，则必须删除最低元素并需要添加新元素。
这种方法的时间复杂度为O(n log k)，因为将新元素添加到PriorityQueue大小的k成本为O(log k)，并且在最坏的情况下，此操作可以执行n多次（因为我们正在迭代大小的数组n）。
请注意，最好的情况时间复杂度为 \xce\xa9(n)，即线性。
\nPriorityQueue因此，根据Big O进行排序和使用 a 之间的差异可以归结为O(n log n)和O(n log k)之间的差异。当k比该方法小得多时n，将带来显着的性能增益。
这是一个实现：
\npublic static int[] getHighestK(int[] arr, int k) {\n Queue<Integer> queue = new PriorityQueue<>();\n \n for (int next: arr) {\n if (queue.size() == k && queue.peek() < next) queue.remove();\n if (queue.size() < k) queue.add(next);\n }\n \n return toIntArray(queue);\n}\n\npublic static int[] toIntArray(Collection<Integer> source) {\n return source.stream().mapToInt(Integer::intValue).toArray();\n}\nmain()
public static void main(String[] args) {\n System.out.println(Arrays.toString(getHighestK(new int[]{3, -1, 3, 12, 7, 8, -5, 9, 27}, 3)));\n}\n输出：
\n[9, 12, 27]\n当给定数组的内容存在一些约束时，我们可以实现O(n)的最坏情况时间复杂度。假设它只包含范围内的数字（当然，你没有被告知，但在面试过程中澄清问题要求总是好的）。[-1000,1000]
在这种情况下，我们可以使用具有线性时间复杂度的计数排序。或者更好的是，只需构建一个直方图（计数排序的第一步）并查看最高值的存储桶，直到看到 K 个计数。（即，实际上并不扩展回完全排序的数组，只需将计数扩展回前 K 个排序元素。）只有当计数数组（可能的输入值）小于计数数组的大小时，创建直方图才有效。输入数组。
\n另一种可能性是给定的数组是部分排序的，由几个排序的块组成。在这种情况下，我们可以使用Timsort，它擅长查找排序运行。它将在线性时间内处理它们。
\nTimsort已经在 Java 中实现，它用于对对象（而不是基元）进行排序。因此，我们可以利用经过良好优化和彻底测试的实现，而不是编写我们自己的实现，这很棒。但由于我们给出了一个原语数组，使用内置的Timsort会产生额外的成本 - 我们需要将数组的内容复制到包装类型的列表（或数组）中。
\n这是一个经典问题，可以通过所谓的 heapselect 来解决， heapselect 是heapsort的一个简单变体。它也可以通过快速选择来解决，但与快速排序一样，它的二次最坏情况时间复杂度很差。
只需保留一个优先级队列（以二叉堆的形式实现），其大小为 k 个最小值。遍历数组，并将值插入堆中（最坏情况 O(log k)）。当优先级队列太大时，删除根处的最小值（最坏情况O(log k)）。遍历完n个数组元素后，你已经删除了nk个最小的元素，所以剩下了k个最大的元素。很容易看出，最坏情况的时间复杂度为 O(n log k)，这比 O(n log n) 更快，但只占用了 O(k) 堆空间。