在排序矩阵中找到一个元素

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

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

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] m,j>n F(m + 1, he, n + 1, we); } else if (matrix[m][n] > t) { // very similar to previous part } } 

算法的运行时间是log（m）+ log（n）。 我正在寻找一种更高效的算法，或者使用简洁的代码。

有了更多评论，我想出了以下代码：

 // return target recurrence in the matrix int F(int[][] m, int rs, int re, int cs, int ce, int t){ int r1 = rs, r2 = re; int c1 = cs, c2 = ce; int r=0 , c = c1; while( r1 < r2 && c1 < c2 ){ // find the last element that =t c = FfirstGreater( r, c1, c2, t); if( c == -1) break; else{ r2 = r; c1 = c; }// else }// else }// while }// f 

以下是函数F1和F2的链接查找排序数组中大于目标的第一个元素

 void FlastLess(int s, int e, int t){ int l = s, h = e; while( l != h ){ int mid = (l+h)/2; if( mid >= t) high = mid - 1; else { if( high < t) low= mid + 1; else low = mid; } } void FfirstGreater(int s, int e, int t){ while(l < h){ mid = (l+h)/2; if ( mid <= t) low = mid+1; else high = mid; } } } 

Answer 1

从矩阵的左下角开始。 然后向右走，直到找到确切的数字（完成），或直到找到更大的数字。

然后你在矩阵中向上，直到找到确切的数字（完成），或直到找到一个太小的数字。

然后再向右移动，……依此类推，直到找到数字或直到你到达矩阵的右侧或顶部。

以下图像包含一些示例，使用Excel表格显示绿色的目标编号，以及黄色跟随的路径。

在最后一个例子中，我们查找207，它不在矩阵中：

这只是算法。 编码留给你作为练习:-)

编辑：当从底行开始时，二进制搜索可能会给出一个更好的起点。 对于算法的其余部分，它可能无关紧要。

Answer 2

您的算法可能是O（log m + log n），但它也给出了错误的答案。

假设您在以下矩阵中搜索“4”（其中左上角是row = 0，col = 0）：

 0 1 4 1 2 5 2 3 6 

您的算法首先查看中心的2 。 由于4大于2 ，因此您继续搜索同一行（不存在），同一列（不存在）和右下角（不存在）。 哎呦。

每个行和列的排序约束实际上非常弱。 特别地，沿对角线的元素可以是任何顺序。

我认为正确的方法是在第一列和最后一列进行二进制搜索，以缩小可能行的范围。 然后对这些行的第一行和最后一行进行二进制搜索，以缩小可能的列。 等等。

不知道如何分析这一个的表现……

Answer 3

这是我会尝试的。 给定m乘n矩阵A ，将值X与条目A(m/2,n/2) （如果需要，使用楼层）。

如果A(m/2,n/2) == X ，那么。

如果A(m/2,n/2) < X ，则需要检查3个较小的矩阵：

 A(1:m/2, 1:n/2) A(1:m/2, n/2+1:n) A(m/2+1:m, 1:n/2) 

如果A(m/2,n/2) > X ，则需要检查3个较小的矩阵：

 A(m/2:m, n/2:n) A(1:m/2, n/2+1:n) A(m/2+1:m, 1:n/2) 

您可以通过将值与相应矩阵中的最小值（左上角值）进行比较来消除其中的两个（并非总是）。 然后，您递归地尝试在每个剩余矩阵中查找值。

其复杂程度约为O((n*m)^0.8) 。

---

行和列排序矩阵是Young画面的特例。 我做了一个谷歌搜索搜索一个年轻的画面，发现这篇文章提供了3个不错的方法 （第一个（也是最差的）是我上面描述的那个）。

Answer 4

对于基于比较的算法，O（lg（m）+ lg（n））查询是最佳的。

certificate

对于基于比较的查询，每个查询只能有两个结果：true或false。 一个明显的扩展是，对于N个查询，您最多可以获得2 ^N个结果。 因此，使用N个查询，您只能在具有最多2 ^N个元素的矩阵中定位元素。

那么搜索mxn矩阵需要多少个查询？ 刚解决N.

2 ^N = mn
lg（2 ^N ）= lg（mn）
N = lg（m）+ lg（n）

因此，lg（m）+ lg（n）查询是最佳的。

基于非比较的查询

该证据是确凿的，但仅适用于基于比较的查询。 如果以不涉及比较的方式查询矩阵，那么如果您知道值的分布，则可以获得接近恒定的时间。 我不会给你一个算法，但我会建议查看Radix排序，因为它包含了击败lg（m）+ lg（n）下限所需的非基于比较的技术。

Answer 5

阅读以前的评论我想出了这个算法。 它基本上假设通过从右上角开始，矩阵可以用作具有一些“循环”的BST（我们不关心这个循环）。

 1 4 9 5 6 10 9 / \ 4 10 / \ / 1 6 \ / 5 

该算法与在BST中搜索相同，并且非常容易理解。 最坏的情况是运行时间为O（n + m）。

 public static boolean search( int[][] matrix, int value ) { int rows = matrix.length; int columns = matrix[0].length; int i = 0; int j = columns - 1; while( i < rows && j >= 0 ) { if( matrix[i][j] == value ) { System.out.println( "Found at " + i + " " + j ); return true; } if( matrix[i][j] < value ) { j--; } else { i++; } } return false; } 

Answer 6

 boolean FindElem(int[][] mat, int elem, int M, int 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++; } } return false; } 

Answer 7

我相信你的算法没有你认为它的时间范围。

为了看到这一点，为简单起见，我们假设您的网格是一个nxn正方形（让我们称之为这个大小为m）。 如果在这种情况下我可以得到与O（log n）不同的时间限制，我可以说你所拥有的不应该是正确的。

特别要注意的是，在最坏的情况下，你会对大小（n / 2）x（n / 2）= m / 4的问题进行三次递归调用。这意味着我们有了重复

 T(1) = 1 T(m) = 3T(m / 4) + O(1) 

使用主定理 ，该函数的运行时间为O（m ^{log ₄ 3} ）= O（n ^{2 log ₄ 3} ）= O（n ^{log ₄ 9} ） ^≈O （n ^1.5849625 ）。 这是ω（log n + log m）; 也就是说，它渐近地严格地更大。

正如许多其他人发布的那样，有几种众所周知的算法在O（m + n）中运行，这些算法的基础是在每一步中向右走一步。 因此，除了正确性，我不建议使用您发布的算法。

Answer 8

给定2d数组中的元素（a [n] [m]）水平和垂直增加。 因此，对于给定的问题，我们需要首先找到元素的索引。 因此，如果我们能够更快地找到元素，那么我们就可以优化解决方案。 问题是我们如何以有效的方式找到它。 一种方法是采用矩阵的中间元素并用它检查给定元素

如果给定元素小于中间元素，那么我们的解决方案位于矩阵a [0] [0]到[n / 2] [m / 2]，因为右边和下面的所有元素都大于中间（因为给定元素少于因此我们将搜索空间从[n] [m]减少到[n / 2] [m / 2]，这是原始大小的四分之一。

如果给定元素大于中间元素那么我们的解决方案不在于矩阵a [0] [0]到[n / 2] [m / 2]，因为左边和上面的所有元素都小于中间（因为给定的元素是大于中间元素）所以我们的搜索空间是总数组减去[0] [0]到[n / 2] [m / 2]，这是原始大小的四分之三。 总数组减去[0] [0]到[n / 2] [m / 2]意味着，将有三个递归调用数组索引

 --------->a[0][m/2](start index) to a[n/2][m](end index) --------->a[n/2][0](start index) to a[n][m/2](end index) --------->a[n/2][m/2](start index) to a[n][m](end index) 

现在递归地根据我们的搜索空间调用相同的函数。

我们的function的时间复杂性如下。 注意：在时间函数中，n表示元素的总数，但不表示所提及的行数.n =（no_of_rows）*（no_of_columns）

  _________________T(n/4) if given element is less than middle of the array. / / T(n)==========------------------- 1 if n=1 (if element found) \ \_________________3T(n/4) if given element is greater than middle element of array 

所以出时间function会

T（n）= 3T（n / 4）或T（n）= T（n / 4）

 In worst case T(n)=3T(n/4) T(n)=3{3T(n/4)} T(n)=3power(i)T(n/(4)poweri) equation------> (1) 

但是T（1）= 1（猜测给定elemet在数组中找到）

 so n/(4power(i))=1 ====> n=2power(2*i) ====> n=2power(2*i) Talking log to base 2 on both sides (log[n])/2=i ====> i=log(sqrt(n)) 

我们得到的是等式1

 T(n)=3power(log[sqrt(n)]) T(n)∈ θ( nlog sqrt(3) ).. 

据我所知，这是一种算法，只需要进行最少量的比较。

Answer 9

JavaScript解决方案：

 //start from the top right corner //if value = el, element is found //if value < el, move to the next row, element can't be in that row since row is sorted //if value > el, move to the previous column, element can't be in that column since column is sorted function find(matrix, el) { var row = 0; //first row var col = matrix[0].length - 1; //last column while (row < matrix.length && col >= 0) { if (matrix[row][col] === el) { //element is found return true; } else if (matrix[row][col] < el) { row++; //move to the next row } else { col--; //move to the previous column } } return false; }