如何从无序列表（例如100个元素）中找到前N（如10）个元素的最佳解决方案？
我想到的解决方案是：1. 使用快速排序算法对列表进行排序，2. 获取前10项。
但是否有更好的替代方案呢？
13个回答
31
时间可以缩短至线性时间：
使用选择算法在线性时间内有效地找到未排序数组中的第k个元素。你可以使用快速排序的变体或更强大的算法。
使用步骤一中得到的枢轴获取前k个元素。
- Yin Zhu
1
2这是非常好的方法。但我要提到线性（确定性）选择实际上相当慢 - 在典型的问题规模上使用随机选择枢轴的快速选择可能会快得多，但它可能需要二次时间。 - j_random_hacker
10
把所有事情委托给Java怎么样？;)
function findTopN(Array list, int n)
{
Set sortedSet<Integer> = new TreeSet<>(Comparators.naturalOrder());
// add all elements from list to sortedSet
// return the first n from sortedSet
}
我并不是想说这是最好的方法。我仍然认为Yin Zhu找到第k大元素的方法是最好的答案。
- nuaavee
2
11TreeSet 会删除重复元素，但这可能不是所期望的。 - Stefan
1一个简单而干净的解决方案，但与选择算法（如快速选择）相比，这将是O(nlogn)的平均/最坏情况，后者可以在O(n)的平均情况下选择前k个元素，并且o时间，其中n是输入数组的大小。 - Pavel
9
如果你处理的是像固定长度整数之类的简单元素，那么只要可以提供与输入数据相同大小的内存缓冲区，就可以使用桶排序或基数排序在O(n)时间内完成排序，这将是最快的方法。
虽然有线性时间的选择算法，但是隐藏常量非常高--约为24。这意味着对于少于几百万个元素的情况，O(nlog n)算法通常更快。
否则，在一般情况下当你只能比较两个元素并确定哪个更大时，问题最好通过堆数据结构解决。
假设您想要 n 个项中的前 k 个。所有基于完全排序数据的解决方案需要O(nlog n)时间，而使用堆仅需要O(nlog k)时间--只需在前k个元素上构建一个堆，然后持续加入一个元素并移除最大值。这将使您得到一个包含最小的k个元素的堆。
- j_random_hacker
4
是的，您可以通过仅保留前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
- Matthew Flaschen
2
1如果所选项目的数量很少，这是很好的。但是，如果要从一百万个元素中选择一万个顶级元素，则不再是最优选择。 - Rafał Dowgird
4
最好的解决方案是使用你所选择的语言提供的任何设施，这将使你的生活更加轻松。然而，如果你想知道应该选择哪个算法，我建议采用不同的方法。如果你谈论的是从100中选出10个，除非你想每秒钟执行很多次，否则通常不必过度担心性能。例如，这段C代码（这是我可以做到最低效的代码）仍然在不到十分之一秒的时间内执行完毕。这还不足够让我考虑去喝咖啡。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#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和所有这些爵士乐。
与所有优化问题一样，先衡量再猜测！
- paxdiablo
4
但这是否是一个合适的面试答案呢？ - zengr
1是的，我相信是这样的。雇用最危险的人是过度设计者。当被要求提供一个计算一系列项总和的函数时，这些人会给你一个可配置处理整数、浮点数、复数并还可以使用回调函数在每个项上执行预计算的 900 行妖怪代码。这不是你想要从事有确定交付日期的项目的人 :-) 此外，这也表明候选人能够独立思考。任何人都可以写出代码。 - paxdiablo
2如果有人能解释为什么他们这样做以及其后果，我会立即雇用他们。请参见https://dev59.com/jXNA5IYBdhLWcg3wk--A#903609和http://stackoverflow.com/questions/445425/what-algorithms-should-every-developer-know/445554#445554，尽管在优点方面存在一些...我们应该说是激烈的...讨论 :-) - paxdiablo
1呵呵，实用性+1... 但至于什么样的答案是最好的，我认为关键是面试者要问：(1) 典型的问题规模是什么？ (2) 需要多快？（顺便说一句，如果在大问题上的性能不重要，那么最好的答案就是“使用语言内置的任何
sort()函数 :-P） - j_random_hacker3
你可以使用
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<Integer> numbers = Lists.newArrayList(1, 3, 8, 2, 6, 4, 7, 5, 9, 0);
final Collector<Integer, ?, List<Integer>> collector = Comparators.greatest(5,
Comparator.<Integer>naturalOrder());
final List<Integer> top = numbers.stream().collect(collector);
System.out.println(top);
}
}
输出结果：[9, 8, 7, 6, 5]
- Pritesh Mhatre
2
你可以在O(n)时间内从未排序的数组中创建一个堆，而且你可以在O(log(n))时间内获取堆的顶部元素。因此，你的总运行时间为O(n + k*log(n))。
- Charles Munger
1
以下是选择排序和插入排序的实现。对于较大的数据集，我建议使用插入排序而不是选择排序。
public interface FindTopValues
{
int[] findTopNValues(int[] data, int n);
}
插入排序实现：
Insertion Sort Implementation:
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<length; i++) {
int curPos = i;
while ((curPos > 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<length; j++) {
if (values[j] > values[maxPos]) {
maxPos = j;
}
}
if (maxPos != i) {
int maxValue = values[maxPos];
values[maxPos] = values[i];
values[i] = maxValue;
}
}
return Arrays.copyOf(values, n);
}
}
- Srihari Konakanchi
0
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<length; j++) {
if (values[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);
}
}
- HARISH
0
我在面试中被要求给出相同的算法。 我完成了，如果有人能将其与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
从包含1亿个初始元素的数组中获取1000个最大整数，平均结果约为400毫秒。还不错！
刚刚尝试了上述的集合：
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]
- Dmitri Algazin
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接