java - 从不同文件夹中的所有文件中找出 100 个最大的数字

Question

我最近接受了一次采访，有人问我以下问题，这对我来说听起来很容易，但最后却变得很棘手。

There are lot of files in all the folders and their sub folders. Each file will have lot of numbers in each line. Given a root folder, I need to find 100 largest number from all those files. I came up with below solution:

• Read all the files line by line.
• Store each number in an array list.
• Sort it in descending order.
• Now get the first k numbers from the list.

但是后来面试官问我这个的时间复杂度是多少。我说因为我们正在对它进行排序所以它会是 O(nlogn) 然后他问我们如何改进下面的程序？由于您将所有内容都存储在内存中，然后对其进行排序 - 如果您不能将所有内容都放入内存怎么办？

当时我很困惑，不知道是否有更好/有效的方法来解决以下问题。他要我写出高效的代码。有没有更好的方法来实现这一点？

下面是我想出的原始代码:

  private static final List<Integer> numbers = new ArrayList<>();

  public static void main(String[] args) {
    int k = 100;
    List<Integer> numbers = findKLargest("/home/david");

    // sort in descending order
    Collections.sort(numbers, Collections.reverseOrder());
    List<Integer> kLargest = new ArrayList<>();
    int j = 0;
    // now iterate all the numbers and get the first k numbers from the list
    for (Integer num : numbers) {
      j++;
      kLargest.add(num);
      if (j == k) {
        break;
      }
    }
    // print the first k numbers
    System.out.println(kLargest);
  }

  /**
   * Read all the numbers from all the files and load it in array list
   * @param rootDirectory
   * @return
   */
  private static List<Integer> findKLargest(String rootDirectory) {
    if (rootDirectory == null || rootDirectory.isEmpty()) {
      return new ArrayList<>();
    }

    File file = new File(rootDirectory);
    for (File entry : file.listFiles()) {
      if (entry.isDirectory()) {
        numbers.addAll(findKLargest(entry.getName()));
      } else {
        try (BufferedReader br = new BufferedReader(new FileReader(entry))) {
          String line;
          while ((line = br.readLine()) != null) {
            numbers.add(Integer.parseInt(line));
          }
        } catch (NumberFormatException | IOException e) {
          e.printStackTrace();
        }
      }
    }
    return numbers;
  }

Answer 1

无需存储所有 N(所有文件中数字的总数)值并对其进行排序，您可以只存储 100 个值 - 每个时刻最大的值。

此任务方便快捷的数据结构 - priority queue (通常基于 binary heap )。创建具有 100 个第一个值的 min-heap，然后为每个新值检查它是否大于堆顶。如果是 - 删除顶部，插入新项目。

空间复杂度是O(K)，时间复杂度是O(NlogK)，这里是K=100，所以可以评估复杂度作为 O(1) 和 O(N)(省略常数项)

展示其工作原理的 Python 示例:

import heapq, random

pq = [random.randint(0, 20) for _ in range(5)]  #initial values
print(pq)
heapq.heapify(pq)                               #initial values ordered in heap
print(pq)
for i in range(5):
    r = random.randint(0, 20)    # add 5 more values
    if r > pq[0]:
        heapq.heappop(pq)
        heapq.heappush(pq, r)
    print(r, pq)

[17, 22, 10, 1, 15]   //initial values
[1, 15, 10, 22, 17]   //heapified, smallest is the left
29 [10, 15, 17, 22, 29]     //29 replaces 1
25 [15, 22, 17, 29, 25]     //25 replaces 10
14 [15, 22, 17, 29, 25]      //14 is too small
8 [15, 22, 17, 29, 25]       //8 is too small
21 [17, 21, 25, 29, 22]     //21 is in the club now