如何在读取 java 中的列表时保留 10 个最大整数？

Question

我有一个列表中的整数列表，我想在迭代列表时保留 10 个最大的整数并将它们保存在 TreeSet 中。我正在使用此代码：

for(Integer i : list) {                
            if (treeSet.size() < 10) {                    
                treeSet.add(i);
            } else if (i > treeSet.last()) {
                treeSet.pollLast();
                treeSet.add(i);
            }
        }

但是当我在运行这段代码之前更改列表中整数的顺序时，结果是不同的。我的代码是真的吗？

Answer 1

treeSet 以升序保存其数据（第一个是最小的），因此您应该替换第一个元素，而不是最后一个：

for(Integer i : list) {                
    if (treeSet.size() < 10) {                    
        treeSet.add(i);
    } else if (i > treeSet.first()) {
        treeSet.pollFirst();
        treeSet.add(i);
    }
}

Answer 2

使用Collection.sort() and get the desired number of results with List.subList().

// Sort the arraylist
Collections.sort(list); 
//gets the last 10 item, last is the largest for ascending default sort
list.subList(list.size()-10, list.size());

Answer 3

尝试使用流（如果可以使用 Java 8）：

final Comparator<Integer> order = Integer::compare;
List<Integer> collect = list.stream().sorted(order.reversed()).limit(10).sorted().collect(Collectors.toList());

您也可以使用 parallelStream() 而不是 stream() ，后者应该更快。

http://blog.takipi.com/new-parallelism-apis-in-java-8-behind-the-glitz-and-glamour/

Answer 4

Warning: Note that your approach is flawed in general (and this flaw is also present in the originally accepted answer): This may deliver wrong results when there are duplicate elements in the list. A random example where I noticed this is an input list like
List<Integer> list = Arrays.asList(
     0, 8, 9, 7, 15, 13, 11, 1, 19, 14, 
     17, 17, 13, 2, 15, 4, 4, 15, 1, 0); 
for which it returns
[1, 7, 8, 9, 11, 13, 14, 15, 17, 19]
instead of
[4, 7, 8, 9, 11, 13, 14, 15, 17, 19]

一个简单直接的解决方案如下：

private static <T> Collection<T> keepLargest(
    List<? extends T> list, Comparator<T> comparator, int n)
{
    TreeSet<T> treeSet = new TreeSet<T>(comparator);
    for(T t : list) 
    {                
        treeSet.add(t);
        while (treeSet.size() > n)
        {
            treeSet.pollFirst();
        }
    }
    return treeSet;
}

可以称为

Collection<Integer> kept = 
    keepLargest(list, Comparator.naturalOrder(), 10);

现在可以争论重复的插入和删除（这是可以避免的），但是由于树集很小，插入的 log(n) 应该可以忽略不计。如果这种性能高度相关，人们也可以考虑使用类似的方法和 PriorityQueue ，或者尝试优化这个解决方案，但在目前的形式下，它非常简单而且不容易出错（过早？ ) 优化。

如何在读取 java 中的列表时保留 10 个最大整数？

how to keep 10 biggest integer while reading a list in java?

java

sorting

collections