java 在已排序矩阵中查找元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6603070/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
find an element in a sorted matrix
提问by SecureFish
Problem: Given a matrix in which each row and each column is sorted, write a method to find an element in it.
问题：给定一个矩阵，其中每一行和每一列都被排序，编写一个方法来查找其中的元素。
It is a classic interview question, here is my solution
这是一个经典的面试问题，这是我的解决方案
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 to [m][n]
F(m + 1, he, n, n);
// find the ele in the area, where i>m,j>n
F(m + 1, he, n + 1, we);
}
else if (matrix[m][n] > t)
{
// very similar to previous part
}
}
The running time of the algorithm is log(m) + log(n). I am looking for an algorithm that is more efficient, or with concise code.
算法的运行时间为log(m) + log(n)。我正在寻找一种更高效或代码简洁的算法。
Having more comments, I come up with following code:
有了更多的评论，我想出了以下代码：
// 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 in column c
r = FlastLess( r1, r2, c, t)
if( r == -1 ) break;
else{
// find the first ele in the row that is >=t
c = FfirstGreater( r, c1, c2, t);
if( c == -1) break;
else{
r2 = r;
c1 = c;
}// else
}// else
}// while
}// f
Here is the link to function F1 and F2 Find the first element in a sorted array that is greater than the target
这是函数 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;
}
}
}
回答by Patrick
Start in the bottom-left corner of your matrix. Then go to the right until you find the exact number (done), or until you find a number that is bigger.
从矩阵的左下角开始。然后向右走，直到找到确切的数字（完成），或者直到找到一个更大的数字。
Then you go upwards in the matrix until you find the exact number (done), or until you find a number that is too small.
然后在矩阵中向上移动，直到找到确切的数字（完成），或者直到找到一个太小的数字。
Then again you move to the right, ... and so on until you found the number or until you reach the right-side or top of your matrix.
然后你再次向右移动，......等等，直到找到数字或直到到达矩阵的右侧或顶部。
The following images contain some examples, using an Excel table showing the target number in green, and the path that is followed in yellow.
下图包含一些示例，使用 Excel 表格以绿色显示目标编号，并以黄色显示跟随的路径。
In the last example we look for 207, which isn't in the matrix:
在最后一个例子中，我们寻找 207，它不在矩阵中：
This is just the algorithm. The coding is left for you as an exercise :-)
这只是算法。编码留给您作为练习:-)
EDIT:When starting on the bottom row, a binary search might give a better starting point. For the rest of the algorithm it probably doesn't matter.
编辑：从底行开始时，二进制搜索可能会提供更好的起点。对于算法的其余部分，它可能无关紧要。
回答by Nemo
Your algorithm may be O(log m + log n), but it also gives the wrong answer.
你的算法可能是 O(log m + log n)，但它也给出了错误的答案。
Suppose you search for "4" in the following matrix (where the upper-left is row=0, col=0):
假设您在以下矩阵中搜索“4”（其中左上角为 row=0, col=0）：
0 1 4
1 2 5
2 3 6
Your algorithm starts by looking at the 2in the center. Since 4is greater than 2, you proceed to search the same row (not there), same column (not there), and the lower-right corner (not there). Whoops.
您的算法首先查看2中心。由于4大于2，您继续搜索同一行（不存在）、同一列（不存在）和右下角（不存在）。哎呀。
The constraint that each row and column is sorted is actually pretty weak. In particular, the elements along the diagonal could be in anyorder.
对每一行和每一列进行排序的约束实际上很弱。特别是，沿对角线的元素可以按任何顺序排列。
I think the correct approach is to do a binary search on the first and lastcolumn to narrow down a range of possible rows. Then do binary search on the first and last of those rows to narrow down the possible columns. And so forth.
我认为正确的方法是对第一列和最后一列进行二分搜索以缩小可能的行范围。然后对这些行的第一行和最后一行进行二分搜索以缩小可能的列。等等。
Not sure how to analyze the performance of this one...
不知道如何分析这个的性能...
回答by PengOne
Here's what I would try. Given an mby nmatrix A, compare the value Xwith the entry A(m/2,n/2)(use floors if necessary).
这就是我要尝试的。给定一个mby nmatrix A，将值X与条目进行比较A(m/2,n/2)（如有必要，请使用楼层）。
If A(m/2,n/2) == X, done.
如果A(m/2,n/2) == X，完成。
If A(m/2,n/2) < X, then there are 3 smaller matrices to check:
如果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)
If A(m/2,n/2) > X, , then there are 3 smaller matrices to check:
如果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)
You can eliminate two of them (not always) by comparing the value to the smallest value in the corresponding matrix (the upper left value). Then you recursively try to find the value in each of the remaining matrices.
您可以通过将值与相应矩阵中的最小值（左上角的值）进行比较来消除其中的两个（并非总是如此）。然后您递归地尝试在每个剩余矩阵中找到值。
The complexity of this is approximately O((n*m)^0.8).
其复杂度约为O((n*m)^0.8).
A row and column sorted matrix is a special case of a Young tableau. I did a google search for searching a Young tableau and found this article which gives 3 nice approaches(the first (and worst) of which is the one I described above).
行和列排序矩阵是Young tableau的特例。我在谷歌上搜索了一个年轻的画面，发现这篇文章提供了 3 种不错的方法（第一个（也是最差的）就是我上面描述的那个）。
回答by Peter Alexander
For a comparison based algorithm, O(lg(m) + lg(n)) queries is optimal.
对于基于比较的算法，O(lg(m) + lg(n)) 次查询是最佳的。
Proof
证明
For a comparison based query, each query can only have two results: true or false. An obvious extension of this is that for N queries you can have at most 2Nresults. Therefore, using N queries, you can only locate elements in a matrix with at most 2Nelements.
对于基于比较的查询，每个查询只能有两个结果：真或假。一个明显的扩展是，对于 N 个查询，您最多可以有 2 N 个结果。因此，使用 N 个查询，您只能在最多 2 N 个元素的矩阵中定位元素。
How many queries then are required to search an m x n matrix? Just solve for N.
那么搜索一个 mxn 矩阵需要多少个查询？只需求解 N。
2N= mn
lg(2N) = lg(mn)
N = lg(m) + lg(n)
2 N= mn
lg(2 N) = lg(mn)
N = lg(m) + lg(n)
Therefore lg(m) + lg(n) queries is optimal.
因此lg(m) + lg(n) 查询是最优的。
Non-comparison based queries
非基于比较的查询
That proof is conclusive, but only for comparison based queries. If you query the matrix in a way that doesn't involve comparisons then you can get near-constant time if you know the distribution of values. I won't give you an algorithm, but I would suggest looking at Radix sortas it contains the kind of non-comparison basedtechniques that are required to beat the lg(m) + lg(n) lower bound.
该证明是决定性的，但仅适用于基于比较的查询。如果您以不涉及比较的方式查询矩阵，那么如果您知道值的分布，则可以获得近乎恒定的时间。我不会给你一个算法，但我建议你看看基数排序，因为它包含了击败 lg(m) + lg(n) 下界所需的那种基于非比较的技术。
回答by Andrea Della Corte
Reading the previous comments I came up with this algorithm. It basically suppose that by starting in the upper-right corner, the matrix can be used as a BST with some "loops" (we don't care about this loops).
阅读之前的评论，我想出了这个算法。它基本上假设通过从右上角开始，矩阵可以用作带有一些“循环”的 BST（我们不关心这些循环）。
1 4 9
5 6 10
9
/ \
4 10
/ \ /
1 6
\ /
5
This algorithm is the same as searching in a BST and is really easy to understand. The worst case run time is O( n + m ).
该算法与在 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;
}
回答by bicepjai
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;
}
回答by Imposter
Given elements in 2d array(be a[n][m]) are increasing horizontally and vertically . So for the given question we need to find the index of the element first. So if we can find the element in quicker way then we can optimize the solution . The question is how do we find it in efficient way. One approach is take the middle element of the matrix and check given element with it
二维数组中的给定元素 (be a[n][m]) 水平和垂直增加。所以对于给定的问题，我们需要先找到元素的索引。因此，如果我们可以更快地找到元素，那么我们就可以优化解决方案。问题是我们如何以有效的方式找到它。一种方法是取矩阵的中间元素并用它检查给定的元素
if given element is lesser than middle element then our solution lies in matrix a[0][0] to a[n/2][m/2] because all elements to right and below are greater than middle (since given element is less than middle element) so we have reduced our search space from a[n][m] to a[n/2][m/2] which is one fourth of original size.
如果给定元素小于中间元素，那么我们的解决方案位于矩阵 a[0][0] 到 a[n/2][m/2] 中，因为右边和下面的所有元素都大于中间元素（因为给定元素小于比中间元素）所以我们将搜索空间从 a[n][m] 减少到 a[n/2][m/2]，这是原始大小的四分之一。
if given element is greater than middle element then our solution doesnt lies in matrices a[0][0] to a[n/2][m/2] because all elements to left and above are lesser than middle (since given element is greater than middle element) so our search space is total array minus a[0][0] to a[n/2][m/2] which is three-fourth of original size. Total array minus a[0][0] to a[n/2][m/2] means ,there will be three recursive call with array index
如果给定元素大于中间元素，那么我们的解决方案不在矩阵 a[0][0] 到 a[n/2][m/2] 中，因为左边和上面的所有元素都小于中间元素（因为给定元素是大于中间元素）所以我们的搜索空间是总数组减去 a[0][0] 到 a[n/2][m/2]，这是原始大小的四分之三。总数组减去 a[0][0] 到 a[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)
Now recursively call the same function based on our search space.
现在根据我们的搜索空间递归调用相同的函数。
Time complexity of our function will as follows . NOTE: In time function n represents total number of element but not no of rows as mentioned .n=(no_of_rows)*(no_of_columns)
我们函数的时间复杂度如下。注意：在时间函数 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
so out time function will
所以超时功能将
T(n)=3T(n/4) or T(n)=T(n/4)
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)
But T(1)=1 (guessing given elemet is found in array)
但是 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))
substituting equation 1 we get
代入方程 1 我们得到
T(n)=3power(log[sqrt(n)])
T(n)∈ θ( nlog sqrt(3) )..
To my knowledge this is the algorithm that takes minimum number of comparisons.
据我所知，这是采用最少比较次数的算法。
回答by spark
JavaScript solution:
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;
}
回答by templatetypedef
I believe that your algorithm does not have the time bounds that you believe that it does.
我相信您的算法没有您认为的时间限制。
To see this, for simplicity let's assume that your grid is an n x n square (let's call this size m). If I can derive a different time bound than O(log n) in this case, I can argue that what you have should not be correct.
为了看到这一点，为了简单起见，让我们假设您的网格是一个 nxn 的正方形（我们称这个大小为 m）。如果在这种情况下我可以得出与 O(log n) 不同的时间界限，我可以争辩说你所拥有的不应该是正确的。
In particular, notice that in the worst case you make three recursive calls to problems that are of size (n / 2) x (n / 2) = m / 4. This means that we have the recurrence
特别要注意，在最坏的情况下，您对大小为 (n / 2) x (n / 2) = m / 4 的问题进行了三个递归调用。这意味着我们有递归
T(1) = 1
T(m) = 3T(m / 4) + O(1)
Using the Master Theorem, the runtime for this function would be O(mlog43) = O(n2 log43) = O(nlog49) ≈ O(n1.5849625). This is ω(log n + log m); that is, it's asymptotically strictly greater.
使用主定理，此函数的运行时间为 O(m log 43) = O(n 2 log 43) = O(n log 49) ≈ O(n 1.5849625)。这是 ω(log n + log m)；也就是说，它渐近严格地更大。
As many other people have posted, there are several well-known algorithms that run in O(m + n) that are based by walking one step in the right direction at each step. Consequently, correctness aside, I would not advise using the algorithm you've posted.
正如许多其他人发布的那样，有几种众所周知的算法在 O(m + n) 中运行，它们的基础是每一步都朝着正确的方向走一步。因此，除了正确性之外，我不建议使用您发布的算法。
