我最近接受了一次采访,有人问我以下问题,这对我来说听起来很容易,但最后却变得很棘手。
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;
}
最佳答案
无需存储所有 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
关于java - 从不同文件夹中的所有文件中找出 100 个最大的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53755715/