查找数组中的前N个元素

在无序列表(例如100)中找到前N个(比如10个)元素的最佳解决方案是什么。

我头脑中的解决方案是1.使用快速排序对其进行排序,2。进入前10名。

但还有更好的选择吗?

时间可以减少到线性时间:

  1. 使用选择算法 ,可以在线性时间内有效地找到未排序数组中的第k个元素。 您可以使用快速排序的变体或更强大的算法。

  2. 使用步骤1中的pivot获取前k个。

如何将所有内容委托给Java;)

function findTopN(Array list, int n) { Set sortedSet = new TreeSet<>(Comparators.naturalOrder()); // add all elements from list to sortedSet // return the first n from sortedSet } 

我并不想说这是最好的方式。 我仍然认为尹朱找到第k个最大元素的方法是最好的答案。

如果你正在处理像固定长度整数这样的简单元素,那么你可以省去与输入数据大小相同的内存缓冲区,可以使用存储桶或基数排序在O(n)时间内完成排序,这样就可以了是最快的。

虽然有线性时间选择算法, 但隐藏常数非常高 – 大约24 。 这意味着对于少于几百万个元素,O(nlog n)算法通常会更快。

否则,在一般情况下,当您只能比较2个元素并确定哪个更大时,问题最好通过堆数据结构来解决。

假设你想要n个项目的前k个。 所有基于对数据进行完全排序的解决方案都需要O(nlog n)时间,而使用堆只需要O(nlog k)时间 – 只需在前k个元素上构建堆,然后继续添加元素并删除最大值。 这将为您留下一个包含最小k个元素的堆。

是的,您可以通过保留前N个(已排序)运行列表在O(n)中执行此操作。您可以使用常规库函数或排序网络对运行列表进行排序 。 例如,使用3的简单演示,并显示运行列表中的哪些元素会更改每次迭代。

5 2 8 7 9

 i = 0 top[0] <= 5 i = 1 top[1] <= 2 i = 2 top[2] <= top[1] (2) top[1] <= top[0] (5) top[0] <= 8 i = 3 top[2] <= top[1] (5) top[1] <= 7 i = 4 top[2] <= top[1] (7) top[1] <= top[0] (8) top[0] <= 9 

最好的解决方案是使用您选择的语言提供的任何设施,这将使您的生活更轻松。

但是,假设这是一个与您应该选择的算法更相关的问题,我将在这里建议一种不同的方法。 如果你说的是100比10,你通常不应该过分担心性能,除非你想每秒多次这样做。

例如,这个C代码(虽然效率低,我可以毫不愚蠢地完成它)仍然需要十分之一秒才能执行。 这还不足以让我考虑去喝咖啡。

 #include  #include  #include  #define SRCSZ 100 #define DSTSZ 10 int main (void) { int unused[SRCSZ], source[SRCSZ], dest[DSTSZ], i, j, pos; srand (time (NULL)); for (i = 0; i < SRCSZ; i++) { unused[i] = 1; source[i] = rand() % 1000; } for (i = 0; i < DSTSZ; i++) { pos = -1; for (j = 0; j < SRCSZ; j++) { if (pos == -1) { if (unused[j]) { pos = j; } } else { if (unused[j] && (source[j] > source[pos])) { pos = j; } } } dest[i] = source[pos]; unused[pos] = 0; } printf ("Source:"); for (i = 0; i < SRCSZ; i++) printf (" %d", source[i]); printf ("\nDest:"); for (i = 0; i < DSTSZ; i++) printf (" %d", dest[i]); printf ("\n"); return 0; } 

通过time运行会给你(我已经将输出格式化了一点以使其可读,但是没有影响结果):

 Source: 403 459 646 467 120 346 430 247 68 312 701 304 707 443 753 433 986 921 513 634 861 741 482 794 679 409 145 93 512 947 19 9 385 208 795 742 851 638 924 637 638 141 382 89 998 713 210 732 784 67 273 628 187 902 42 25 747 471 686 504 255 74 638 610 227 892 156 86 48 133 63 234 639 899 815 986 750 177 413 581 899 494 292 359 60 106 944 926 257 370 310 726 393 800 986 827 856 835 66 183 901 Dest: 998 986 986 986 947 944 926 924 921 902 real 0m0.063s user 0m0.046s sys 0m0.031s 

只有一旦数量变大,你通常会担心。 别误会我的意思,我不是说你不应该考虑性能。 你不应该做的是花太多时间来优化无关紧要的事情 - YAGNI和所有那些爵士乐。

与所有优化问题一样, 测量不要猜!

好吧,你可以在O(n)时间从未排序的数组创建一个堆,并且你可以在O(log(n))时间内从堆中获取顶部元素。 所以你的总运行时间是O(n + k * log(n))。

写在选择排序和插入排序实现下面。 对于较大的数据集,我建议使用排序比选择排序更好

 public interface FindTopValues { int[] findTopNValues(int[] data, int n); } 

插入排序实现:

 public class FindTopValuesInsertionSortImpl implements FindTopValues { /** * Finds list of the highest 'n' values in the source list, ordered naturally, * with the highest value at the start of the array and returns it */ @Override public int[] findTopNValues(int[] values, int n) { int length = values.length; for (int i=1; i 0) && (values[i] > values[curPos-1])) { curPos--; } if (curPos != i) { int element = values[i]; System.arraycopy(values, curPos, values, curPos+1, (i-curPos)); values[curPos] = element; } } return Arrays.copyOf(values, n); } } 

选择排序实施:

 public class FindTopValuesSelectionSortImpl implements FindTopValues { /** * Finds list of the highest 'n' values in the source list, ordered naturally, * with the highest value at the start of the array and returns it */ @Override public int[] findTopNValues(int[] values, int n) { int length = values.length; for (int i=0; i<=n; i++) { int maxPos = i; for (int j=i+1; j values[maxPos]) { maxPos = j; } } if (maxPos != i) { int maxValue = values[maxPos]; values[maxPos] = values[i]; values[i] = maxValue; } } return Arrays.copyOf(values, n); } } 

是的,有一种方法比quicksort更好。 正如Yin Zhu指出的那样,您可以先搜索第k个最大元素,然后使用该元素值作为分割数组的轴

我在面试时被要求使用相同的算法。 我这样做了,如果有人可以用Java中最快的算法来比较它 – 将非常有用。

  public int[] findTopNValues(int[] anyOldOrderValues, int n) { if (n < 0) { return new int[]{}; } if (n == 1) { return new int[]{findMaxValue(anyOldOrderValues)}; } int[] result = new int[n + 1]; for (int i = 0; i < Math.min(n, anyOldOrderValues.length); i++) { result[i] = anyOldOrderValues[i]; } Arrays.sort(result); int max = result[0]; for (int i = n - 1; i < anyOldOrderValues.length; i++) { int value = anyOldOrderValues[i]; if (max < value) { result[n] = value; Arrays.sort(result); int[] result1 = new int[n + 1]; System.arraycopy(result, 1, result1, 0, n); result = result1; max = result[0]; } } return convertAndFlip(result, n); } public static int[] convertAndFlip(int[] integers, int n) { int[] result = new int[n]; int j = 0; for (int i = n - 1; i > -1; i--) { result[j++] = integers[i]; } return result; } 

并测试:

 public void testFindTopNValues() throws Exception { final int N = 100000000; final int MAX_VALUE = 100000000; final int returnArray = 1000; final int repeatTimes = 5; FindTopValuesArraySorting arraySorting = new FindTopValuesArraySorting(); int[] randomArray = createRandomArray(N, MAX_VALUE); for (int i = 0; i < repeatTimes; i++) { long start = System.currentTimeMillis(); int[] topNValues = arraySorting.findTopNValues(randomArray, returnArray); long stop = System.currentTimeMillis(); System.out.println("findTopNValues() from " + N + " elements, where MAX value=" + (MAX_VALUE - 1) + " and return array size " + returnArray + " elements : " + (stop - start) + "msec"); // System.out.println("Result list = " + Arrays.toString(topNValues)); } } private static int[] createRandomArray(int n, int maxValue) { Random r = new Random(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = r.nextInt(maxValue); } return arr; } 

结果如下:

 findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 395msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 311msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 473msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 380msec findTopNValues() from 100000000 elements, where MAX value=99999999 and return array size 1000 elements : 406msec 

〜400msc的平均结果,用于从100.000.000个初始元素的数组中获得1000个最大整数。 不错!

刚试过上面那套:

 findTopNValues() from 101 elements and return array size 10 elements : 1msec Result list = [998, 986, 986, 986, 947, 944, 926, 924, 921, 902] Original list = [403, 459, 646, 467, 120, 346, 430, 247, 68, 312, 701, 304, 707, 443, 753, 433, 986, 921, 513, 634, 861, 741, 482, 794, 679, 409, 145, 93, 512, 947, 19, 9, 385, 208, 795, 742, 851, 638, 924, 637, 638, 141, 382, 89, 998, 713, 210, 732, 784, 67, 273, 628, 187, 902, 42, 25, 747, 471, 686, 504, 255, 74, 638, 610, 227, 892, 156, 86, 48, 133, 63, 234, 639, 899, 815, 986, 750, 177, 413, 581, 899, 494, 292, 359, 60, 106, 944, 926, 257, 370, 310, 726, 393, 800, 986, 827, 856, 835, 66, 183, 901] 

最好的算法将取决于K的大小。如果K很小,那么通过简单地遵循BubbleSort算法并且迭代外循环K次将给出前K个值。 复杂性将是O(n * k)。

然而,对于接近n的K值,复杂度将接近O(n ^ 2)。 在这种情况下,快速排序可能是一个很好的选择。

 public class FindTopValuesSelectionSortImpl implements FindTopValues { /** * Finds list of the highest 'n' values in the source list, ordered naturally, * with the highest value at the start of the array and returns it */ @Override public int[] findTopNValues(int[] values, int n) { int length = values.length; for (int i=0; i<=n; i++) { int maxPos = i; for (int j=i+1; j values[maxPos]) { maxPos = j; } } if (maxPos != i) { int maxValue = values[maxPos]; values[maxPos] = values[i];**strong text** values[i] = maxValue; } } return Arrays.copyOf(values, n); } } 

您可以使用List并使用guava的Comparators类来获得所需的结果。 这是一个高度优化的解决方案。 请参阅下面的示例,其中包含前5个数字。 Api可以在这里找到。

 import java.util.Comparator; import java.util.List; import java.util.stream.Collector; import org.junit.Test; import com.google.common.collect.Comparators; import com.google.common.collect.Lists; public class TestComparator { @Test public void testTopN() { final List numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0); final Collector> collector = Comparators.greatest(5, Comparator.naturalOrder()); final List top = numbers.stream().collect(collector); System.out.println(top); } } 

输出:[9,8,7,6,5]