求两个有序数组的第k大值

求两个有序数组的第k大值

那么有没有更好的方案？我们可以考虑从k入手。如果我们每次能够删除一个一定处于第k大元素之前的元素，那么需要进行k次。但是如果我们每次都能删除一半呢？可以利用A，B有序的信息，类似二分查找，也是充分利用有序。
假设A 和B 的元素个数都大于k/2，我们将A 的第k/2 个元素（即A[k/2-1]）和B 的第k/2个元素（即B[k/2-1]）进行比较，有以下三种情况（为了简化这里先假设k 为偶数，所得到的结论对于k 是奇数也是成立的）：
- A[k/2 - 1] == B[k/2 - 1];
- A[k/2 - 1] > B[k/2 - 1];
- A[k/2 - 1] < B[k/2 - 1];
如果A[k/2 - 1] < B[k/2 - 1] ，意味着 A[0] 到 A[k/2 - 1] 的元素一定小于 A+B 第k大的元素。因此可以放心的删除A数组中的这k/2个元素；
同理，A[k/2 - 1] > B[k/2 - 1];可以删除B数组中的k/2个元素；
当A[k/2 - 1] == B[k/2 - 1] 时，说明找到了第k大的元素，直接返回A[k/2 - 1] 或B[k/2 - 1]的值。
因此可以写一个递归实现，递归终止条件是什么呢？
- A或B为空时，直接返回A[k-1] 或 B[k-1]
- 当k = 1时，返回min(A[0], B[0]) //第1小表示第一个元素
- 当A[k/2 - 1] == B[k/2 - 1] 时，返回A[k/2 - 1] 或B[k/2 - 1]

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息