40

假设我有一个矩阵 ( MxN)，它的行和列已排序。

  1. 每行中的所有元素都按升序排列
  2. 每列中的所有元素都按升序排列
  3. 所有元素都是整数

  4. 无法做出其他假设

    例子：

    [1 5 8 20]

    [2 9 19 21]

    [12 15 25 30]

我必须找出矩阵中是否存在给定的数字（基本搜索）。我有一个运行的算法O(n)

int row = 0;
int col = N-1;

while (row < M && col >= 0) {
  if (mat[row][col] == elem) { 
    return true;
  } else if (mat[row][col] > elem) { 
    col--;
  } else { 
    row++;
  } 
}

但有人问我一个O(log (MxN)) == O(Log(n))解决方案。有任何想法吗？？

4

5 回答 5

76

O(log (M * N)) 解决方案对于此任务是不可能的。

让我们看一个简化的任务：在“排序”方阵中，假设次对角线（绿色）上方的所有元素都小于给定数字，次对角线（红色）下方的所有元素都大于给定数字，并且对次对角线上的元素没有额外的假设（黄色的）。

在此处输入图像描述

这项任务的原始假设和这些额外的假设都没有告诉我们次对角线上的元素是如何相互关联的。这意味着我们只有一个未排序的 N 个整数数组。我们无法比 O(N) 更快地在未排序的数组中找到给定的数字。因此，对于方阵的原始（更复杂）问题，我们无法得到比 O(N) 更好的解决方案。

对于矩形矩阵，拉伸正方形图片并相应地设置附加假设。这里我们有 min(N,M) 个大小为 max(N,M)/min(N,M) 的排序子数组。这里最好的搜索方法是使用线性搜索来找到一个或多个可能包含给定值的子数组，然后在这些子数组中使用二分查找。在最坏的情况下，需要在每个子数组中进行二分搜索。复杂度为 O(min(N,M) * (1 + log(max(N,M) / min(N,M))))。因此，对于矩形矩阵的原始（更复杂）问题，我们无法得到比 O(min(N,M) * ( 1 + log(max(N,M)) - log(min(N,M))) 更好的解决方案）。

于 2012-05-15T09:25:46.393 回答
7

不可能比 O(n) 做得更好。有些人（这个页面上至少有三个人）认为他们可以做得更好，但那是因为他们的算法是错误的，或者因为他们不知道如何计算他们算法的复杂性，所以他们试图猜测它。这篇博文非常好，将向您解释这些人的错误。

O(n) 最优的证明草稿：考虑以下矩阵：

1     2     3     4     5     6 … (n-2)  (n-1) (n+1)
2     3     4     5     6     7 … (n-1)  (n+1) (n+2)
3     4     5     6     7     8 … (n+1)  (n+2) (n+3)
…     …     …     …     …     … … …      …     …
(n-2) (n-1) …     …     …     … … …      …     (2n-1)
(n-1) (n+1) …     …     …     … … …      …     2n
(n+1) (n+2) …     …     …     … … (2n-1) 2n    (2n+1)

如果您n在此矩阵中查找，则必须为每行至少检查一次是否n在该行中，因为n可能在任何行中。（证明不完整，但这里是想法）

于 2012-05-14T22:20:33.593 回答
4

你必须使用递归来解决这个问题。给定一个矩阵 X 和数字 y，您可以在 X 的中间行对 y 进行二分搜索，并将矩阵分成四个部分，这样：

A|B
---
C|D

A 中的所有元素都小于 y，D 中的所有元素都大于 y，并且 y 可以在 B 和 C 中。迭代地在 B 和 C 中找到 y。

由于 height(A)=height(B)\approx= height(C)=height(D), size(X)>= 2*(size(B)+size(C)) 。因此，如果 O(logn)，则产生的复杂性。

def find(X,y):
    a,b = X.shape
    i = a /2
    j = binsearch(X[i,:], y)
    if X[i,j]==y:
        return True
    else:
        return find( X[ (i+1):a, 0:(j-1)], y ) or find( X[ 0:i, j:b], y )
于 2012-05-14T21:28:04.400 回答
2

由于行和列都是排序的，如果我们查看每一行的第一个元素，我们可以找到哪个包含我们要查找的数字。然后，再次，我们可以利用每一行中的元素已排序并找到该数字的事实。
我知道最快的搜索算法是二分搜索，它的复杂度为 O(log n)，所以总复杂度为 O(log m + log n)。
这是一个示例，假设我们要查找 28：

 1  2  3  4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
  • 我们对第一列（1、11、21、31、41）的元素进行二分查找，发现该行是第三行，因为它的第一个元素小于我们的数字，但下一行的第一个元素更大。步数：2（21、31、找到）
  • 我们再次对第三行（21、22、23、24、25、26、27、28、29、30）进行二分搜索并找到我们的数字。步数：2 - 3（25、27 或 28，找到）
于 2012-05-14T19:46:21.263 回答
0

我认为这可以在 O(log(n*n)*log(n)) 时间内完成，其中 n 是否。方阵的行数。

根据 Matrix 的性质，矩阵的主对角线是一个有序数组。因此，我们可以在 O(log(n)) 中搜索一个元素或其下限。现在，使用这个元素作为枢轴，我们有 4 个子矩阵。我们可以说子矩阵（左上）中的所有元素都更小，子矩阵（右下）中的所有元素都更大。因此，我们可以将其从搜索空间中删除。

现在，在子矩阵（右上）和子矩阵（左下）中递归搜索。

因为，在每一步，我们执行一次 log(n) 搜索（沿着主对角线），最多可以有 log(n*n) 步（因为我们在每一步中将搜索空间减少了一半）。

因此，时间复杂度 = O(log(n) log(n n))。

如有不妥请指正。

参考 - [书]破解编码面试（问题 11.6）

于 2014-10-28T15:22:31.363 回答