相关疑难解决方法(0)

我最近接受了这个面试问题,我很好奇它是一个很好的解决方案.

假设我有一个二维数组,其中数组中的所有数字从左到右,从上到下依次递增.

搜索和确定目标号码是否在阵列中的最佳方法是什么？

现在,我的第一个倾向是利用二进制搜索,因为我的数据已经排序.我可以确定O(log N)时间内的数字是否在一行中.然而,正是这两个方向让我失望.

我认为可能有用的另一种解决方案是从中间的某个地方开始.如果中间值小于我的目标,那么我可以确定它在中间的矩阵的左方形部分.然后我沿着对角线移动并再次检查,减小了目标可能存在的方格的大小,直到我对目标数字进行了磨练.

有没有人有解决这个问题的好主意？

示例数组:

从左到右,从上到下排序.

1  2  4  5  6  
2  3  5  7  8  
4  6  8  9  10  
5  8  9  10 11  

假设我有一个矩阵(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))解决方案.有任何想法吗？？

这个问题不是作业,只是出于个人兴趣,主要是我的好奇心

我的教授在课堂上谈了这个问题一段时间,但他没有多说这个.以下是问题:

给定mxn矩阵A,其整数元素分别沿水平和垂直方向排序.我需要开发一个递归程序来搜索查询值a是否在A中.讨论设计的时间复杂度.

所以我想了一会儿.我的第一种方法是检查基本情况:第一个元素和最后一个元素

检查第一个元素>项目是否检查最后一个元素<item

项目是我想要找到的

这是假想矩阵:(x可以是任意数字,但此矩阵垂直和水平排序)

             first     x          x        x         x
                 x     x          x        x         x
                 x     x         mid       x         x
                 x     x          x        x         x
                 x     x          x        x         last

在检查基本情况并确保我想要找到的"项目"在此矩阵的范围内之后,我不知道是否可以从矩阵中的"mid"进行检查(如二进制搜索).如果item <mid,则将焦点放在左半边.如果item> mid,则将焦点放在右半边.

但是,然后我尝试制作一个像下面这样的矩阵,我的"项目"是10

                 1     2          3        4         5
                 2     4          7        8          9
                 3     6          10       11         12

如果我按照我之前说过的方式:由于10大于中间的"7",我专注于正确的部分.然后我检查"8",因为10大于"8",我搜索右边的部分.但是10不是正确的......

任何人都可以给我一些想法或洞察力如何解决这个问题？非常感谢

可能重复:
给定一个从左到右,从上到下按升序排序的二维数组,搜索目标数的最佳方法是什么？
搜索已排序的2D矩阵

一种时间有效的程序,用于在二维矩阵中查找元素,其行和列单调增加.(行和列从上到下,从左到右).

如果2D数组已经排序,我只能想到二分搜索.

我正在尝试写一个线性时间算法O(n),它给出一个表A [0..n-1] (用升序自然值填充)检查是否有一对A [i],A [j]满足f(A [i],A [j])= C (C是预定常数).

假设f(a,b)= a + b算法将是:

Algo Paires(A[0..N-1], C)
in: Tab A[0..n-1] and C a constant
out : Boolean
Init indice ? 0
For i ? 0..n-1 do 
    if indice ? i & A[indice] + A[i] = C 
      return true
    else if i = n-1 & indice ? n-2 
      indice++; i ? 0;
End for
return False

但如果:

算法会是什么呢？有什么建议 ？