这是一个家庭作业问题.他们说,这需要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*N矩阵.对所有行进行排序,并对所有列进行排序.找到矩阵的第K个最大元素.
在n ^ 2中执行它很简单,我们可以使用堆或合并排序(n lg n)对其进行排序然后得到它,但是有更好的方法,比(n lg n)更好吗？
数组示例::
1 5 7 12
3 6 8 14
4 9 10 15
11 17 19 20
与其他行和列类似,1 <5 <7 <12和1 <3 <4 <11.现在说我们需要找到第10个最小的元素,在这里它是11..hope这增加了一些细节问题......