java - 检查一个数组是否大于另一个

Question

给定两个整数数组 A 和 B，返回真当且仅当。对于 A 中的每个整数，B 中都有一个更大的整数。需要进行 1 到 1 映射，A 中的每个整数都必须在 B 中找到自己的更大整数。

例子:

int[] A = {1, 1, 5, 3};
int[] B = {7, 5, 2, 3};
boolean result = isGreater(A,B); 

/* 
result is true because:

A[0] < B[2], 
A[1] < B[3],
A[2] < B[0], 
A[3] < B[1].

Every integer in A found its greater integer in B. Note that multiple mappings can exist,
finding one is enough to return true.
*/

我目前的解决方案是 O(n^2)，我为 A 中的每个元素迭代 B。有没有更好的方法？

Answer 1

您可以在 O(n logn) 中完成。

1. 对两个列表进行排序 - O(n logn)
2. 使用与合并排序的 merge 例程相似¹ 例程遍历两个数组，尝试找到其更大的整数伙伴 - O (n)

---

¹ 在合并排序的合并例程中，我们比较两个正在运行的索引指向的两个数字(每个数组中的一个)并选择较小(或较大)的数字并将其存储在一个新的array 并将我们从中选择元素的索引移动一个。但在这里，必须是一对一的映射。