在O（log n）中的排序矩阵（行n列）中查找数字

  • Z时代
  • 2024-01-10
  • 分类：问答

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

回答：

O（log（M * N））解决方案无法完成此任务。

让我们看一个简化的任务：在“排序的”方矩阵中，假设次要对角线（绿色）上方的所有元素均小于给定数，次要对角线（红色）下方的所有元素均大于给定数，并且次要对角线上的元素（黄色）。

在此处输入图片说明

该任务的原始假设或这些附加假设都没有告诉我们次要对角线上的元素如何相互关联。这意味着我们只有N个整数的未排序数组。我们无法在未排序的数组中找到给定的数字快于O（N）。因此，对于原始的（较复杂的）方矩阵问题，我们无法获得比O（N）更好的解决方案。

对于矩形矩阵，拉伸正方形图片并相应地设置其他假设。在这里，我们有大小分别为max（N，M）/

min（N，M）的min（N，M）个排序的子数组。最好的搜索方法是使用线性搜索来查找一个或几个可能包含给定值的子数组，然后在这些子数组中使用二进制搜索。在最坏的情况下，有必要在每个子阵列中进行二进制搜索。复杂度为O（min（N，M）（1+ log（max（N，M）/min（N，M）））））。所以对于矩形矩阵的原始问题（更复杂的问题），我们无法获得比O（min（N，M）（1 +log（max（N，M））-log（min（N，M）））更好的解决方案）。

以上是 在O（log n）中的排序矩阵（行n列）中查找数字 的全部内容， 来源链接： utcz.com/qa/401803.html

回到顶部