如何高效地在有序矩阵中搜索？

Question

如何高效地在有序矩阵中搜索？

28

我有一个 x 乘以 y 的矩阵，其中每行和每列都按如下升序排列。

1   5   7    9
4   6   10   15
8   11  12   19
14  16  18   21

如何在O(x+y)的时间复杂度内搜索这个矩阵中的数字？

我在面试中被问到了这个问题，但是我无法想出方法。很好奇是否有解决办法。

- Ashley

类似于这个：http://geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-about-algorithms-10 - Rohan Monga

3个回答

5

将矩阵分成4个子矩阵。如果子矩阵右下角的元素小于关键字，则丢弃该子矩阵。如果子矩阵左上角的元素大于关键字，则丢弃该子矩阵。重复进行剩余子矩阵的拆分过程。

[更新] 有关伪代码（以及复杂性讨论），请参见Jeffrey L Whitledge在此问题中的答案。

- Landei

那应该有更好的性能：O(log x + log y) ?! - Andre Holzner

可能会更快，但需要更多的内存。 - Landei

你将如何将矩阵分成4个子矩阵？你会重复到什么时候？你将如何知道元素不存在？开始编写伪代码，你很快就会发现这并不容易。 @Landei - 内存不是与x*y相同吗？ - Manoj R

实际上，这将是O(2 ^ log x + 2 ^ log y)，因为每一步都需要递归处理2个（或3个，但可以优化以避免这种情况）子矩阵。这是O（x + y）。 - Chris Dodd

0

// the matrix is like this, from left to right is ascending, and
// from down to up is ascending, but the second row'start is not always bigger than the first row's end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/
// 1   5   7    9
// 4   6   10   15
// 8   11  12   19
// 14  16  18   21
// time complexity is O(x+y), x is the count of row, and y is the count of column

public boolean searchMatrix2(int[][] matrix, int target) {
    int rowCount = matrix.length;
    if(rowCount == 0) return false;

    int colCount = matrix[0].length;
    if(colCount == 0) return false;

    //first find the target row, needs O(x)
    int targetRow = 0;
    while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) {
        targetRow++;
    }
    //than find the target in the target row, needs O(y), so the total is O(x)+O(y)
    boolean result = false;
    for(int i = 0; i < colCount; i ++) {
        if(matrix[targetRow][i] == target) {
            result = true;
            break;
        }
    }
    return result;
}

其实，我们可以使用二分查找两次，首先通过二分查找找到目标行，然后再通过二分查找在该行中找到目标，因此时间复杂度为O(lgx) + O(lgy)，即O(lgx + lgy)，比O(x+y)更好。

- Converse Chen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- codaddict · Accepted Answer

从第一行的最后一个元素（右上角）开始。
将其与key进行比较。我们有3种情况：

如果它们相等，则完成搜索。
如果key大于该元素，则说明key不能出现在该行中，因此向下移动搜索到下一个元素。
如果key小于该元素，则说明key可能出现在该行靠左的位置，但不能出现在更接近下面的列中，因此向左移动搜索到下一个元素。

继续这样做，直到找到该元素或无法继续移动（即不存在该键）。

伪代码：

Let R be number of rows
Let C be number of columns

Let i = 0
Let j = C-1

found = false
while( i>=0 && i<R) && (j>=0 && j<C) )
   if (matrix[i][j] == key )
      found = true
      break
   else if( matrix[i][j] > key )
       j--
   else if( matrix[i][j] < key )
       i++
end-while