找到一个排序矩阵的元素 [英] find an element in a sorted matrix
问题描述
问题： 给定的矩阵，其中每行和每列进行排序，写一个方法来找到在它的元件。
这是一个典型的面试问题，这里是我的解决方案
布尔F（INT [] []矩阵，诠释HS，诠释他，INT WS，诠释我们）
{
如果（HS＆GT;他|| WS＆gt;我们）
返回false;
INT M =（HS +他）/ 2;
INT N =（WS +我们）/ 2;
如果（矩阵[米] [n]的== t）的
{
返回true;
}
否则如果（矩阵[米] [n]的＆其中; t）的
{
//找到ELE同一行中，从右到[米] [n]的
F（M，M，N + 1，我们）;
//找到ELE在同一关口，上部为[米] [n]的
F（M + 1，他，N，N）;
//发现在该地区的ELE其中i＆GT M，J＆GT; N
F（m + 1个，他，n + 1个，我们）;
}
否则如果（矩阵[米] [N]≥吨）
{
//非常相似，previous部分
}
}
该算法的运行时间是log（M）+的log（n）。我在寻找一种算法是比较有效的，或以简洁code。
有更多的评论，我想出了以下code：
//将目标复发矩阵
INT F（INT [] []男，诠释RS，INT重，诠释CS，INT CE，诠释T）{
INT R1 = RS，R 2 =重;
INT C1 = CS，C2 = CE;
INT R = 0，C = C1;
而（R1＆LT; R2和放大器;＆安培; C1＆LT; C2）{
//找到最后一个元素＆LT; = T C列
R = FlastLess（R1，R2，C，T）
如果（R == -1）打破;
其他{
//发现是与GT的行中的第一ELE; =吨
C = FfirstGreater（R，C1，C2，吨）;
如果（C == -1）打破;
其他{
R2 = R;
C1 = C;
}// 其他
}// 其他
}// 而
}// F
下面是功能F1和F2的链路 <一href="http://stackoverflow.com/questions/6553970/find-the-first-element-in-an-array-that-is-greater-than-the-target">find在数组的第一个元素是大于目标的
无效FlastLess（int类型，诠释E，INT T）{
INT L = S，H = E;
而（升！= H）{
INT中期=（1 + H）/ 2;
如果（中＆GT; = T）=高中旬 - 1;
其他 {
如果（高＆LT;吨）低=中等+ 1;
其他低=中等;
}
}
无效FfirstGreater（int类型，诠释E，INT T）{
而（L＆LT; H）{
中期=（1 + H）/ 2;
如果（中＆LT; = T）低=中等+ 1;
其他高=中间;
}
}
}
开始在你的矩阵的左下角。然后往右走，直到找到确切的数目（完成），或者直到你找到一个数字，这是更大的。
然后你在矩阵中去向上，直到找到确切的数目（完成），或者直到你找到一个数字，这是太小了。
然后再移动到右侧，......依此类推，直到你找到的号码或直到你到达右侧的矩阵或顶部。
下面的图像包含了一些例子，使用Excel表格显示为绿色的目标数量，以及随后在黄色的道路。
在我们寻找207的最后一个例子，这是不是在矩阵：
这仅仅是算法。编码是留给你作为练习： - ）
编辑：：当在最后一行开始，二进制搜索可能会给一个更好的起点。对于该算法它可能并不重要的其余部分。
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.
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 an array that is greater than the target
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;
}
}
}
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.
In the last example we look for 207, which isn't in the matrix:
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.
这篇关于找到一个排序矩阵的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
