<分区>
我在一次采访中被问到这个问题。显然我能够在 O(n) 时间内完成,但我没有想出一种在 O(logn) 中解决的方法。这听起来像是在使用一些分而治之的算法,但我不确定。
<分区>
我在一次采访中被问到这个问题。显然我能够在 O(n) 时间内完成,但我没有想出一种在 O(logn) 中解决的方法。这听起来像是在使用一些分而治之的算法,但我不确定。
最佳答案
将两者都截断到大小 k。如有必要,让程序在一个或两个数组的末尾想象足够多的无穷大,使它们达到大小 k;这不会影响渐近运行时。 (在实际实现中,我们可能会做一些更有效率的事情。)
然后,比较每个数组的第 k/2 个元素。如果元素比较相等,我们就找到了第 k 个元素;否则,让第k/2个元素较低的数组为A,另一个为B。扔掉A的下半部分和B的上半部分,然后递归找到剩下的第k/2个元素。当我们达到 k=1 时停止。
在每一步中,保证 A 的下半部分太小,而 B 的上半部分保证太大。剩余的第 k/2 个元素保证大于 A 的下半部分,因此它保证是原始元素的第 k 个元素。
概念证明,使用 Python:
def kth(array1, array2, k):
# Basic proof of concept. This doesn't handle a bunch of edge cases
# that a real implementation should handle.
# Limitations:
# Requires numpy arrays for efficient slicing.
# Requires k to be a power of 2
# Requires array1 and array2 to be of length exactly k
if k == 1:
return min(array1[0], array2[0])
mid = k//2 - 1
if array1[mid] > array2[mid]:
array1, array2 = array2, array1
return kth(array1[k//2:], array2[:k//2], k//2)
我测试过这个,但不多。
关于java - 我有 2 个排序的整数数组,如何在 O(logn) 时间内找到第 k 个最大的项目?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21965884/