给定两个数组 A 和 B，每个数组的大小都是 N 如何找到其中的第 K 大元素集合 X = {i x j | i ∈ A 和 j ∈ B}?
我提出了 O(N^2 log(n)) 解决方案，方法是形成集合 X，对其进行排序，然后在 K< 处找到元素 从最后一个位置。有没有更好的复杂度更低的解决方案？
最佳答案
给定一个候选编号，您可以使用 A 和 B 的排序表示中的两个指针在时间 O(N) 中检查它在集合 {i x j | i ∈ A 和 j ∈ B}。因此，一种可能的解决方案是对 i x j 的值使用二进制搜索，运行时间为 O(N * (log N + log U))，其中 U 是从中提取 A 和 B 的宇宙的大小。
关于arrays - 两个数组所有可能乘积中的第 k 个最大元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45126635/