3

矩阵 A 按行和列排序，其中 A[i][j] < A[i][j+1] 和 A[i][j] < A[i+1][j]。附加信息是每行的第一个元素小于前一行的最后一个元素，例如：

⎡1  3   5  17⎤
⎢2  4   6  18⎥
⎣7  9  11  20⎦

而且我对这些附加信息在确定 O(lgn) 复杂性中所起的作用感到困惑。

我可以想出 O(m) + O(n) 如下：

int search(int mat[4][4], int n, int x)
{
   int i = 0, j = n-1;  //set indexes for top right element
   while ( i < n && j >= 0 )
   {
       if ( mat[i][j] == x )
       {
          printf("\n Found at %d, %d", i, j);
          return 1;
       }
       if ( mat[i][j] > x )
           j--;
       else //  if mat[i][j] < x
           i++;
       }

       printf("\n Element not found");
       return 0;  // if ( i==n || j== -1 )
  }

但我认为我没有使用过信息：每行的第一个元素小于上一行的最后一个元素

谁能给我一些提示？另外，这不是家庭作业。谢谢！

4

1 回答 1

1

您当前正在做的是详尽的搜索（即检查每个元素一次），因此 O(n*m)。您没有利用矩阵的排序特性。

给定一个排序列表，二分搜索允许您在 O(lg n) 中进行搜索。基本上，您检查列表的中间元素。如果它大于您的目标，那么您知道您可以忽略列表的后半部分。重复此过程，每次将搜索空间减半，直到找到元素或搜索空间等于 1 项。在 Python 代码中：

import math

def binSearch(value, data):
    bottom = 0 #first entry
    top = len(data) -1 #last entry

    while bottom <= top: #if bottom ever becomes greater than top then the object is not in the list
        i = int(bottom + math.floor((top - bottom)/2)) #find the mid-point
        if data[i] == value: #we found it
            return i
        elif data[i] > value:
            top = i - 1 #value must be before i
        else:
            bottom = i + 1 #value must be after i

    return None #not found

现在，想想你可以从矩阵结构中收集到什么信息。您知道mat，对于任何 row i，按照您的描述排序的给定 anxm 矩阵mat[i][0]是该行中最低的项目并且mat[i][n]是最高的。类似地，对于任何列 j，mat[0][j]是该列的最低值并且mat[m][j]是最高值。这意味着如果mat[i][0] <= value <= mat[i][n]不为真，则值不能在第 i 行中。同样，如果mat[0][j] <= value <= mat[m][j]不为真，则值不能在 j 列中。

因此，明显的改进是，对于可能包含该值的每一行，进行二分搜索。

for row in mat:
    if (row[0] <= value) AND (row[len(row) - 1] >= value): #if the value could possibly be in the row
        result = binSearch(value, row)

        if result: #if we found it
            return result

binSearch()是 O(lg m)。最坏的情况是binSearch()在每一行上执行，因此 O(n * lg m)。

我试图实现一个 O(lg n * lg m) 解决方案，但我无法弄清楚。问题是我只能消除矩阵的左上角和右下角。我无法消除左下角或右上角。

于 2012-06-19T05:49:17.753 回答