algorithm - 在大小为 n 的两个数组中找到第 n 个最大数的算法

Question

我有这个问题：

给定两个大小为 n 的排序列表（存储在数组中），找到一个 O(log n) 算法，计算两个列表并集中的第 n 个最大元素。

我可以看到这里可能有一个技巧，因为它需要第 n 个最大元素，并且数组的大小也为 n，但我不知道它是什么。我在想我可以适应计数排序，这行得通吗？

Answer 1

比较 A[n/2] 和 B[n/2]。如果相等，它们中的任何一个都是我们的结果。该算法的其他停止条件是当两个数组的大小均为 1 时（最初或在几个递归步骤之后）。在这种情况下，我们只选择 A[n/2] 和 B[n/2] 中的最大值。

如果 A[n/2] < B[n/2]，则对 A[] 的后半部分和 B[] 的前半部分递归地重复此过程。

如果 A[n/2] > B[n/2]，则对 B[] 的后半部分和 A[] 的前半部分递归地重复此过程。

由于在每一步问题大小（在最坏的情况下）减半，我们将得到 O(log n) 算法。

---

始终将数组大小除以 2 以使索引仅在n2 的幂时才能正常工作。选择索引（对于任意n）更正确的方法是对一个数组使用相同的策略，但为另一个数组选择补充索引j=n-i。

Answer 2

Evgeny Kluev 给出了一个更好的答案——我的答案是 O(n log n)，因为我不认为它们是被排序的。

我可以添加的是一个非常好的视频的链接，该视频解释了二进制搜索，由 MIT 提供：

https://www.youtube.com/watch?v=UNHQ7CRsEtU

Answer 3

public static void main(String[] args) {  


int[] fred = { 60, 5, 7, 3, 20, 3, 44 };  

int[] tmp = new int[fred.length];  
go(fred, 1, tmp, 3);  
}  

public static void go(int[] fred, int cnt, int[] tmp, int whatPosition) {  
int max = 0;  
int currentPosition = 0;  
for (int i = 0; i < fred.length; i++) {  
if (i == 0)  
max = fred[i];  
else {  
if (fred[i] > max) {  
max = fred[i];  
currentPosition = i;  
}  
}  
}  
System.arraycopy(fred, 0, tmp, 0, fred.length);  
tmp[currentPosition] = 0;  
cnt++;  
if(cnt != whatPosition)  
go(tmp, cnt, tmp, whatPosition);  
else{  
for (int i = 0; i < tmp.length; i++) {  
if (i == 0)  
max = tmp[i];  
else {  
if (tmp[i] > max) {  
max = tmp[i];  
}  
}  
}  
System.out.println(max);  
}  




}