我最近接受了这个面试问题,我很好奇它是一个很好的解决方案.
假设我有一个二维数组,其中数组中的所有数字从左到右,从上到下依次递增.
搜索和确定目标号码是否在阵列中的最佳方法是什么？
现在,我的第一个倾向是利用二进制搜索,因为我的数据已经排序.我可以确定O(log N)时间内的数字是否在一行中.然而,正是这两个方向让我失望.
我认为可能有用的另一种解决方案是从中间的某个地方开始.如果中间值小于我的目标,那么我可以确定它在中间的矩阵的左方形部分.然后我沿着对角线移动并再次检查,减小了目标可能存在的方格的大小,直到我对目标数字进行了磨练.
有没有人有解决这个问题的好主意？
示例数组:
从左到右,从上到下排序.
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
这是一个谷歌面试问题:
给定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这增加了一些细节问题......
M是整数的二维矩阵(nXm),它们在行和列中排序写一个函数搜索(int s),它返回数字或Null的确切位置.最有效的方法是什么？