这是一个家庭作业问题.他们说,这需要O(logN + logM)地方N和M是数组的长度.
让我们命名的数组a和b.显然我们可以忽略所有a[i]和b[i]i> k.
首先,让我们来比较一下a[k/2]和b[k/2].让b[k/2]> a[k/2].因此我们也可以丢弃所有b[i],其中i> k/2.
现在我们拥有所有a[i],我<k和所有b[i],其中我<k/2找到答案.
你下一步怎么做？
我有这个问题:
给定大小为n的两个排序列表(存储在数组中),找到一个O(log n)算法,该算法计算两个列表的并集中的第n个最大元素.
我可以看到这里可能有一个技巧,因为它需要第n个最大的元素,并且数组的大小也是n,但我无法弄清楚它是什么.我以为我可以适应计数排序,那会有用吗？
我已经实现了一个工作功能.但它效率不高,因为它会在每次调用中复制一个新副本.我无法将其转换为仅使用a_start,a_end,b_start,b_end.我已经尝试了几种方法来转换它,但它们都没有适用于所有情况.我如何转换它,以便它接收数组a和b的开始和结束指针？我已经尝试了以下内容并修改了ki-1和kj-1,这样它只需要k,但是没有用.
int m = a_right-a_left, n=b_right-b_left;
int i = (a_left+a_right)/2;
or int i = (int)((m* (k-1)) / (m+n) );
下面是我的工作代码,每次调用使用一个新的数组副本.
public static int kthSmallest(int[] a, int[] b, int k) {
if (a.length==0)
return b[k-1];
else if (b.length==0)
return a[k-1];
else if (b.length<a.length)
return kthSmallest(b, a, k);
// make sure i + j = k - 1
int m = a.length, n=b.length;
int i = (int)((double)m / (m+n) * (k-1)); // make sure i won't be out of bounds
int j …