在时间复杂度为O(lgm) + O(lgn)的排序矩阵(MXn)中查找特定值
矩阵A按行和列排序，其中Ai < Ai和Ai < Ai+1。附加信息是每行的第一个元素小于前一行的最后一个元素，例如：
⎡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 )
}但我认为我没有使用这些信息:每行的第一个元素比前一行的最后一个元素小
有谁能给我一些提示吗？再说这不是家庭作业。谢谢!
回答 1
Stack Overflow用户
发布于 2012-06-19 13:49:18
您当前所做的是一个详尽的搜索(即检查每个元素一次)，因此O(n*m)。您没有利用矩阵的排序特性。
给定一个排序列表，Binary Search允许您以O(lg )进行搜索。基本上，您检查列表的中间元素。如果它大于你的目标，那么你知道你可以忽略列表的后半部分。重复此过程，每次将搜索空间减半，直到找到元素或搜索空间等于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现在，考虑一下您可以从矩阵结构中收集哪些信息。您知道，给定一个按照您所述排序的n x m矩阵mat，对于任何行i，mat[i][0]是该行中最低的项，而mat[i][n]是最高的项。类似地，对于任何列j，mat[0][j]是该列的最低值，而mat[m][j]是最高值。这意味着如果mat[i][0] <= value <= mat[i][n]不为真，则value不能在第i行中。同样，如果mat[0][j] <= value <= mat[m][j]不为真，则value不能在列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 resultbinSearch()为O(lg )。最坏的情况是对每一行执行binSearch()，因此是O(n * lg )。
我试图实现一个O(lg * lg )的解决方案，但是我想不出来。问题是我只能消除矩阵的左上角和右下角。我不能去掉左下角或右上角。
https://stackoverflow.com/questions/10627345
复制相似问题
腾讯云开发者
