相关疑难解决方法(0)

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

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

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

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

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

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

示例数组:

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

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

问题:给定一个矩阵,其中每行和每列都被排序,编写一个方法来查找其中的元素.

这是一个经典的面试问题,这是我的解决方案

boolean F(int[][] matrix, int hs, int he, int ws, int we)
{
    if (hs > he || ws > we) 
        return false; 

    int m = (hs + he) / 2; 
    int n = (ws + we) / 2;

    if (matrix[m][n] == t)
    {
        return true;
    }
    else if (matrix[m][n] < t)
    {
        // find the ele in the same row, right to [m][n]
        F(m, m, n + 1, we);

        // find the ele in the same col, upper …

M是整数的二维矩阵(nXm),它们在行和列中排序写一个函数搜索(int s),它返回数字或Null的确切位置.最有效的方法是什么？

鉴于以下问题,我很感激任何更正,因为我对当前的问题没有解决方案(取自我教授的一个考试!!!):

备注:这不是功课!

问题:

给定两个排序的数组A(具有长度n)和B(具有长度m),每个数组

element(在两个数组中)是一个实数和一个数字X(也是一个实数),

我们想知道是否存在a ? A和b ? B,如:

a + b = X ,在O(n+m)运行时间.

方案:

首先,我们从两个数组的末尾开始检查,因为我们不需要大于的数字X:

• 我= n

• k = m

• 而A [i]> X,i = i -1

• 而B [k]> X,k = k -1

定义j = 0.现在开始从当前的iin A和jin中开始运行B:

• while i > 0 , j < k :
• if A[i]+B[j] == X ,然后返回两个单元格
• 其他 …

给出了一个在所有三个维度中排序的 3d 矩阵，我们必须在其中找到一个给定的数字。

对于上述问题，我一直在思考：3D 数组arr[m][n][r]就像一堆矩形，其中每个矩形（考虑arr[m][n][0]）将最大元素作为最低的最右边元素（arr[m-1][n-1][0]）。我们可以在 中的每个矩形内搜索O(m+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(m+n+r)）。我对吗 ？

有没有人有其他想法？复杂性如何？