我最近在一次面试中进行了一次编码测试。有人告诉我：
有一个由一百万个
ints组成的大型未排序数组。用户希望检索K最大的元素。你会实现什么算法？
在此过程中，有人强烈暗示我需要对数组进行排序。
因此，我建议使用内置的sort()，或者如果性能真的很重要的话，可以使用自定义实现。然后我被告知，使用Collection或数组来存储最大的k，对于循环，可以实现大约O(N)，事后来看，我认为它是O(N*k)，因为每次迭代都需要与K大小的数组进行比较，以找到要替换的最小元素，而对数组进行排序的需要会导致代码至少为O(N log N)。
然后，我查看了SO上的这个链接，该链接建议K编号的优先级队列，每次找到较大的元素时删除最小的编号，这也将给出O(N log N)。编写一个程序，从10亿个数字的数组中找出100个最大的数字
for循环方法坏吗？我应该如何证明使用for循环或priorityqueue/排序方法的利弊？我认为，如果数组已经排序，则无需再次迭代整个数组，也就是说，如果对排序后的数组调用了其他检索方法，则它应该是恒定时间。在运行实际代码时，是否有一些性能因素是我在理论伪代码时没有考虑的？
解决此问题的另一种方法是使用Quickselect。这将为您提供O(n)的总平均时间复杂度。考虑一下：
- 使用Quickselect(O(n))查找k第四个最大数x
- 再次遍历数组(或仅遍历右侧分区)(O(n))并保存所有元素≥x
- 返回保存的元素
(如果有重复的元素，您可以通过计算需要添加到结果中的x的重复次数来避免它们。)
你的问题和你链接到的SO问题中的问题的区别在于，你只有一百万个元素，所以它们肯定可以保存在内存中，以便正常使用Quickselect。
有一个由一百万个int组成的大型未排序数组。用户想要检索
K最大的元素。在此过程中，有人强烈暗示我需要对数组进行排序。
因此，我建议使用内置的
sort()或自定义实现
我想这并不是一个暗示，而是一种欺骗你的把戏(测试你的知识有多强)。
如果您选择使用内置的Dual Pivot Quicksort对整个源数组进行排序来解决此问题，则无法获得比O(n log n)更好的时间复杂性。
相反，我们可以维护一个PriorytyQueue来存储结果。在对每个元素的源数组进行迭代时，我们需要检查队列是否已达到大小K，如果不是，则元素应添加到队列中，否则(大小等于K)，我们需要将下一个元素与队列中最低的元素进行比较-如果下一个元件更小或相等，我们应该忽略。如果它更大，则必须删除最低的元素，并且需要添加新元素。
这种方法的时间复杂度将是O(n log k)，因为向大小为k的PriorytyQueue中添加新元素将花费O(k)并且在最坏的情况下，该操作可以执行n次(因为我们在大小为n的数组上迭代)。
请注意，最佳情况下的时间复杂度为 Ω(n)，即线性。
因此，根据Big O排序和使用 O(n logk)这里有一个实现： 输出： 当存在关于给定数组内容的一些约束时，我们可以实现O(n)的最坏情况时间复杂性。假设它只包含 在这种情况下，我们可以使用计数排序，它具有线性时间复杂性。或者更好的方法是，只需构建直方图(计数排序的第一步)，然后查看值最高的桶，直到您看到K个计数。(即，不要实际扩展回完全排序的数组，只需将计数扩展回排序前K个元素。)只有当计数数组(可能的输入值)小于输入数组的大小时，创建直方图才有效。 另一种可能性是，给定的数组是部分排序的，由几个排序的块组成。在这种情况下，我们可以使用Timsort，它善于查找排序的运行。它将在线性时间内处理它们。 Timsort已经在Java中实现，它用于对对象(而不是基元)进行排序。因此，我们可以利用经过充分优化和彻底测试的实现，而不是编写自己的实现，这很好。但是，由于我们得到了一个基元数组，使用内置的Timsort会有额外的成本——我们需要将数组的内容复制到包装器类型的列表(或数组)中。PriorytyQueue之间的差异可以归结为O(n log n)和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)排序
[-1000,1000]范围内的数字(当然，你还没有被告知这一点，但在面试中澄清问题要求总是很好的)。
这是一个经典的问题，可以通过所谓的heapselect来解决，这是heapsort的一个简单变体。它也可以用quickselect来解决，但与quicksort一样，它具有较差的二次最坏情况时间复杂性。
只需保留一个优先级队列，实现为二进制堆，大小为k最小值的k。遍历数组，并将值插入堆中(最坏情况为O(logk))。当优先级队列太大时，删除根的最小值(最坏情况O(log k))。经过n个数组元素后，您已经删除了n-k个最小的元素，因此保留了k个最大的元素。很容易看出，最坏情况下的时间复杂度是O(n-logk)，它比O(n-log n)更快，代价是堆只有O(k)空间。
这里有一个想法。我会考虑创建最大大小为(2147483647)的数组(int)，因为它是int的最大值(214748364)。然后，对于我从原始数组中得到的每个数字，只需在我创建的空数组中放入相同的索引(作为数字)+1。
因此，在这篇文章的结尾，我将为每个人提供类似[1,0,2,0,3](我创建的数组)的东西，它们表示数字[0, 2, 2, 4, 4, 4](初始数组)。
因此，为了找到K最大的元素，您可以对创建的数组进行反向for，并在每次有不同的元素时从K倒计数到0，然后为0。例如，如果你有2，你必须把这个数字数2次。
这种方法的局限性在于，由于数组的性质，它只适用于整数。。。
此外，java中int的表示形式是-2147483648到2147483647，这意味着在需要创建的数组中，只能放置正数。
注意：若您知道存在int的最大值，那个么您可以用该最大值来降低创建的数组大小。例如，如果最大int为1000，那么您需要创建的数组大小为1000，然后此算法应该执行得非常快。
我认为您误解了排序所需的内容。
您需要对K大小的列表进行排序，而不需要对原始N大小的输入数组进行排序。这样，在最坏的情况下，时间复杂性将为O(N*log(K))(假设您几乎每次都需要更新K大小的列表)。
要求说N很大，但K要小得多，所以O(N*log(K))也比O(N*log(N))小。
您只需要为每个大于前面第K个最大元素的记录更新K大小的列表。对于N远大于K的随机分布列表，这将是可以忽略的，因此时间复杂性将更接近O(N)。
对于K大小的列表，您可以看看是否有一个具有固定容量和自定义比较器的PriorityQueue实现，它使用带有一些附加逻辑的优先级队列。
有一种算法可以在最坏情况下实现这一点，时间复杂度O(n*log(k))具有非常好的时间常数(因为只有一次通过原始数组，并且只有在输入数据表现良好的情况下，才会相对地访问日志(k) (*)请注意，如果某些最高的k值在源集中重复出现，A可以返回重复值。您可以通过搜索操作来避免这种情况，以确保v还不在a中。您还想为此找到一个合适的数据结构(因为优先级队列具有线性复杂性)，即辅助哈希表或平衡二进制搜索树或类似的东西，这两种都在 java.util.PriorityQueue有助于保证其操作的时间复杂性： 此实现为查询和反查询方法(offer、poll、remove()和add)提供了O(log(n))时间；remove(Object)和contains(Object)方法的线性时间；以及检索方法(peek、element和size)的恒定时间。 注意，如上所述，我们只从A中删除最低(第一)元素，因此我们喜欢O(log(k))。如果您想避免重复，如上所述，那么您还需要搜索添加到其中的任何新值(使用O(k))，这将使您面临最坏的总体情况，即在预排序输入数组的情况下，O(n*k)，而不是O，其中每个元素v都会引发内部循环。java.util中可用。