谷歌的采访问题

Question

可能重复：

Given a 2d array sorted in increasing order from left to right and top to bottom, what is the best way to search for a target number?

以下是在谷歌的采访中提出的问题：

给您一个存储整数的2D数组，垂直和水平排序。

编写一个以整数作为输入并输出一个bool的方法，说明该整数是否在数组中。

做这件事最好的方法是什么？它的时间复杂度是多少？

Answer 1

首先，我会询问“纵向和横向排序”的具体含义。

如果矩阵的排序方式是每行的最后一个元素小于下一行的第一个元素，则可以在第一列上运行二进制搜索，以确定该行是哪一行，然后在该行上运行另一个二进制搜索。该算法将占用O(log + log )时间，其中C和R分别是行数和列数。使用对数的属性，如果N是数组中的元素数，则可以将其写入O(log(C*R))，这与O(log )相同。这几乎等同于将数组视为一维，并在其上运行二进制搜索。

但是，矩阵的排序方式可以是每一行的最后一个元素不少于下一行的第一个元素：

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. 车床，漂洗，重复，直到你找到一个，或者你没有更多的元素可考虑；

这种方法也是对元素数的对数。

Answer 2

从矩阵的左下角开始，按照下面所述的规则遍历矩阵：

矩阵遍历基于以下条件：

如果输入数字大于当前数字:移动Right

• If输入号小于当前数字:移动Up.

• If输入号等于当前数字:返回Success

• If输入号不等于当前数字，也不可能转换:返回Fail

时间复杂性：(感谢Martinho )

时间复杂度为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 3

想到的第一个方法是垂直二进制搜索，然后是当您找到它应该在的行时的水平搜索。复杂性将是O(log NM)，其中N和M是数组的维度。

进一步的解释:只考虑每一行的第一个数目。当您为指定的数字执行这些第一个数字的二进制搜索时，如果幸运的话，结果将是指定的数字，否则它将是指定号码之前或之后的位置，这取决于二进制搜索实现。一旦您找到指定数字之间的第一个数字中的两个，您就知道该数字位于该行中，第二个二进制搜索将在该行中找到该数字。