java - 查找 Long(在列表中)是否适合 Long 值列表

Question

我有一个 List<Long> (A) 指示可用于不同分区的免费大小。 用户上门询问List<Long> ( B) 表示他们要存储的文件大小。

现在，如果任何 Long(来自 B)可以放入 A 中的任何空闲大小，我们要重新使用该分区，否则为它们创建新分区。

我怎么知道 Long 中是否有任何一个？ B 的值小于 Long 中的任何一个在 A.

如果我使用迭代方法扫描 A 并找出是否有任何 B 适合，这将导致 O(n^2) 运行时间，但我们可以做得更好吗？

是否存在针对此类问题的任何数据结构？

Answer 1

这是一个 O(n) 的解决方案:

给定:

List<Long> A; // size n
List<Long> B; // size m

找到两条边:

long a = Collections.max(A);  // O(n)
long b = Collections.min(B);  // O(m)

然后看最大的A能不能装下最小的B:

boolean canFit = a >= b; // O(1)

整体时间复杂度为 O(n + m)，对于 n 约等于 m 为 O(n)。