来自Google的采访问题

Question

可能重复:
给定一个从左到右,从上到下按升序排序的二维数组,搜索目标数的最佳方法是什么？

在Google采访中询问了以下内容:

您将获得一个存储整数的2D数组,垂直和水平排序.

编写一个方法,将整数作为输入,并输出一个bool说明整数是否在数组中.

做这个的最好方式是什么？它的时间复杂度是多少？

Answer 1

开始在左下角矩阵的角落,并按照下列规定遍历矩阵的规则:

矩阵遍历基于以下条件:

1. 如果输入的数字大于当前数字:向右移动
2. 如果输入的数量小于当前号码:移动向上.
3. 如果输入的数字等于当前数字:返回成功
4. 如果输入数字不等于当前数字且无法转换:返回失败

时间复杂性:(感谢Martinho Fernandes)

时间复杂度为O(N + M).在最坏的情况下,搜索的元素位于左上角,这意味着你会上升N次,然后离开M次.

例

输入矩阵:

--------------
| 1 | 4 | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| *3* | 8 | 10 |
--------------

要搜索的数字:4

步骤1: 从您有3个(左下角)的单元格开始.

3 <4:向右移动

| 1 | 4 | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| 3 | *8* | 10 |
--------------

第2步: 8> 4:向上移动

| 1 | 4 | 6  | 
--------------
| 2 | *5* | 9  |
--------------
| 3 | 8 | 10 |
--------------

第3步:5> 4:向上移动

| 1 | *4* | 6  | 
--------------
| 2 | 5 | 9  |
--------------
| 3 | 8 | 10 |
--------------

第4步:

4 = 4:返回数字的索引

Answer 2

我首先会询问有关"垂直和水平排序"的含义的详细信息

如果矩阵的排序方式是每行的最后一个元素小于下一行的第一个元素,则可以在第一列上运行二进制搜索,以找出该行所在的行,然后运行另一行行上的二进制搜索.该算法将采用O(log C + log R)时间,其中C和R分别是行数和列数.如果N是数组中元素的数量,则使用对数属性,可以将其写为O(log(C*R)),它与O(log N)相同.这几乎与将数组视为1D并在其上运行二进制搜索相同.

但是矩阵的排序方式应该是每行的最后一个元素不小于下一行的第一个元素:

1 2 3 4 5 6 7 8  9
2 3 4 5 6 7 8 9  10
3 4 5 6 7 8 9 10 11

在这种情况下,您可以同时运行某种水平垂直二进制搜索:

1. 测试第一列的中间数.如果它小于目标,请考虑它上面的线.如果它更大,请考虑以下内容;
2. 测试第一个考虑的行的中间数.如果它更少,请考虑它左边的列.如果它更大,请考虑右边的那些;
3. 车床,冲洗,重复,直到找到一个,或者你没有更多的元素要考虑;

该方法也是元素数量的对数.