我最近接受了这个面试问题,我很好奇它是一个很好的解决方案.
假设我有一个二维数组,其中数组中的所有数字从左到右,从上到下依次递增.
搜索和确定目标号码是否在阵列中的最佳方法是什么？
现在,我的第一个倾向是利用二进制搜索,因为我的数据已经排序.我可以确定O(log N)时间内的数字是否在一行中.然而,正是这两个方向让我失望.
我认为可能有用的另一种解决方案是从中间的某个地方开始.如果中间值小于我的目标,那么我可以确定它在中间的矩阵的左方形部分.然后我沿着对角线移动并再次检查,减小了目标可能存在的方格的大小,直到我对目标数字进行了磨练.
有没有人有解决这个问题的好主意？
示例数组:
从左到右,从上到下排序.
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
在最近的Java电话采访中我被问到这个问题:
您将获得具有以下属性的NxN二进制(0-1)矩阵:
例:
0 1 1
1 1 1
0 0 1
每行中的位值被排序,行表示整数3,7和1.
找到表示最小整数的行.在上面的示例中,答案是第3行,它表示整数1.
我从二次复杂的蛮力开始.采访者回答说我没有利用排序的财产.
在思考了很多之后,我在每一行都使用了二元搜索,然后它来到了O(nlogn).他问我是否可以进一步改进.我想了很多但没有改进.
如果有人能提出任何关于改进它的指示,我将不胜感激.
另一个例子:
0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1
答案是第3行,代表整数0.