java – 在无限列表中查找最高的N个数字

发布时间：2020-12-15 05:12:25 所属栏目：Java 来源：网络整理

导读：我在最近的一次 Java访谈中被问到了这个问题. Given a List containing millions of items,maintain a list of the highest n items. Sorting the list in descending order then taking the first n items is definitely not efficient due to the list siz

我在最近的一次 Java访谈中被问到了这个问题.

Given a List containing millions of items,maintain a list of the highest n items. Sorting the list in descending order then taking the first n items is definitely not efficient due to the list size.

以下是我所做的,如果有人能提供更高效或更优雅的解决方案,我会很感激,因为我相信这也可以使用PriorityQueue来解决：

public TreeSet<Integer> findTopNNumbersInLargeList(final List<Integer> largeNumbersList,final int highestValCount) {

    TreeSet<Integer> highestNNumbers = new TreeSet<Integer>();

    for (int number : largeNumbersList) {
        if (highestNNumbers.size() < highestValCount) {
            highestNNumbers.add(number);
        } else {
            for (int i : highestNNumbers) {
                if (i < number) {
                    highestNNumbers.remove(i);
                    highestNNumbers.add(number);
                    break;
                }
            }
        }
    }
    return highestNNumbers;
}

解决方法

您不需要嵌套循环,只需保持插入并在集合太大时删除最小的数字：

public Set<Integer> findTopNNumbersInLargeList(final List<Integer> largeNumbersList,final int highestValCount) {

  TreeSet<Integer> highestNNumbers = new TreeSet<Integer>();

  for (int number : largeNumbersList) {
    highestNNumbers.add(number);
    if (highestNNumbers.size() > highestValCount) {
      highestNNumbers.pollFirst();
    }
  }
  return highestNNumbers;
}

相同的代码也应该与PriorityQueue一起使用.在任何情况下,运行时应该是O(n log highestValCount).

附：正如在另一个答案中指出的那样,您可以通过跟踪最低数量来避免不必要的插入,从而进一步优化(以可读性为代价).

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!