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