2

如何在按行排序的 2D nxn 矩阵中搜索元素。可以通过O(nlogn)对每一行使用二进制搜索和对每一行O(nlog(logn))使用插值搜索来完成。有什么O(n)解决办法吗？

约束：数组包含整数。

示例：在给定的 5x5 矩阵中搜索 32。

0 5 6 8 42 98

-4 -1 3 21 455

-4 0 3 4 4

0 0 0 0 0

0 [32] 64 244 333

请帮忙。

4

2 回答 2

0

在矩阵M [m*n]（m 行，n 列）中搜索x 。 我认为最好的选择是不正确的跳行。 - 如果 x 超出行（r）的范围，则跳过其中的搜索 除此之外，只需应用二进制（或索引位近似）搜索


const int n=...;
const int m=...;
double x=...,A[m][n]={...};
int r,i,j,j0; 
double *p;
// init bit mask for index approximation
for (j=1;j<n;j<<=1); j>>=1; if (!j) j=1; j0=j;
// search
for (r=0;r<m;r++)   // all rows
 if (x>=A[r][0])    // skip if x is too low
  if (x<=A[r][n-1]) // skip if x is too high
   {
   // index approximation search in row r
   for (p=A[r],i=0,j=j0;j;j>>=1)
    {
    i|=j;
    if ((i>=n)||(x<p[i])) i^=j;
    if (x==p[i]) return "x found in A[r][i]";
    }
   }
return "x not found";

在复杂度上，你的 N 是 m*n，算法是：

Omin(m+  log2(n))
Omax(m+m*log2(n))

if (m==n) 那么我们可以更简单地以 N=n*n 的顺序重写它：

Omin(sqrt(N)+   log2(sqrt(N)) )
Omax(sqrt(N)*(1+log2(sqrt(N))))

如果不是，则 n->N/m 和 m->N/n 所以：

Omin((N/n)+   log2(sqrt(N/m)) )
Omax((N/n)*(1+log2(sqrt(N/m))))

如您所见，复杂性很大程度上取决于矩阵值，并且从 Omin 到 Omax。应该更改程序以满足您的界面和环境，并且返回值只是为了显示发生了什么，应该更改以满足您的需求。

于 2013-10-19T08:14:25.690 回答
-1

虽然是一个相当古老的帖子，但仍然如此。

从右上角或左下角（您可以选择的任何一侧）开始。假设我们选择右上角。将密钥与矩阵元素进行比较。

 if(key==matrix[i][j])
      return true;
   if(key<matrix[i][j])
         then move towards left(j--)
   else      //if the key is greater than the matrix element
         then move towards down (i++);

最坏情况的时间复杂度是当我们需要遍历一整行和一整列时，因此 O(n+n) =O(n)。

于 2016-11-04T09:52:08.853 回答