arrays - 排序数组以找到前 20 个最小的数字

Question

<分区>

Answer 1

你有两个选择

1. 对数组进行排序，拉出小端的 20 个元素(取决于你对数组排序的方向，对吧？)
2. 保留数组元素的有序集合(由于数组的非唯一性，可能不是集合)。添加数组中的前 20 个元素。每次您发现一个小于“好集合”中最高元素的元素时，用这个新元素替换最高元素。

第二个可能看起来更慢，但它实际上取决于数组的大小。您可以一次遍历数组来完成此操作，因此最好在 80 亿左右的数组上执行此操作。

编辑:第一个算法是O(n lg n)。第二种算法是 O(k n)，这里的 k 是 20(您需要前 20 个)。因此，当 lg n > 20 或 n > 2^20 或 n > ~1000000 时，第二种算法更快。因此，如果您的属性(property)少于一百万，您最好进行分类。如果您的 Assets 超过一百万，您最好制作外部列表并一次性通过。