Google的一道面试题

Question

可能是重复问题:
给定一个从左到右、从上到下递增的二维数组，最好的方法是什么来搜索目标数字？

以下内容是在Google面试中提出的：

你有一个存储整数的二维数组，按垂直和水平方向排序。

编写一个方法，以整数作为输入，并输出一个布尔值，指示该整数是否在数组中。

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

- Josh Morrison

---

问题是什么？ - user470379

它是按哪个方向排序的（即从左到右，从上到下=最小->最大）？ - atp

给定一个从左到右和从上到下排序的二维数组，找出数组中是否存在目标元素的最快方法是什么？ - payne

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 |
--------------

第二步： 8 > 4：向上移动

---

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

第三步： 5 > 4：向上移动

---

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

第四步：

4=4：返回该数的索引

- rkg

---

为什么这个可以工作？它的时间复杂度是多少？对于面试问题，特别重要的是要证明你的推理。 - templatetypedef

我认为你把左右弄混了。除此之外，这是一个不错的解决方案。 - IVlad

@Ravi：时间复杂度为O(N+M)。在最坏的情况下，要查找的元素位于左上角，这意味着您需要向上移动N次，向左移动M次。 - R. Martinho Fernandes

@Martinho：谢谢！已经包含在答案中了。 - rkg

Answer 2

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

如果矩阵按照每行的最后一个元素小于下一行的第一个元素的方式进行排序，您可以在第一列上运行二分搜索以找到该数字所在的行，然后在该行上再运行另一个二分搜索。这个算法将花费O(log C + log R)时间，其中C和R分别是行数和列数。利用对数的一个性质，可以将其写为O(log(C*R))，如果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. 重复以上步骤，直到找到一个，或者没有更多要考虑的元素;

这种方法在元素数量上也是对数级的。

- R. Martinho Fernandes

---

你怎么知道它在哪一行？我认为这样做不会起作用，因为仅仅通过查看第一列是无法确定它是否在某一行中的。你可以知道它肯定不在某一行中，但这并没有什么帮助。 - IVlad

Answer 3

首先想到的方法是进行垂直二分查找，然后在找到应该在的行时进行水平查找。复杂度将为O(log NM)，其中N和M是数组的维数。

进一步解释： 考虑每行的第一个数字。当您对这些第一个数字执行二分搜索以查找指定数字时，结果将是指定数字（如果您很幸运），否则它将是指定数字所在位置之前或之后的位置，具体取决于二分搜索实现方式。一旦找到了指定数字应该放置在其两个第一个数字之间的行，您就知道该数字在该行中，并且第二次二分搜索将在该行中查找该数字。

- user470379

---

它可以分成多行。并不一定非得放在一行中。 - ypercubeᵀᴹ

垂直二分查找将给出它应该在的行。 - user470379

你如何通过二分查找找到应该在哪一行？你无法保证它会在你搜索返回的行中。 - IVlad

考虑矩阵的行为 1 2 3 | 3 4 100 | 4 5 1000。我们想要搜索 100。您的二分查找将返回最后一行，而 100 不是该行的一部分。接下来怎么办？ - IVlad

基于这个问题的其他答案，我同意，但我认为问题的文字应该改变。 - user470379