Проблема: Учитывая матрицу, в которой сортируются каждая строка и каждый столбец, напишите метод, чтобы найти в нем элемент.
Это классический вопрос интервью, вот мое решение
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
}
}
Время работы алгоритма: 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 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
Вот ссылка на функцию 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;
}
}
}
