我有一个 x
乘以 y
的矩阵,其中每行和每列都按如下升序排列。
1 5 7 9
4 6 10 15
8 11 12 19
14 16 18 21
如何在O(x+y)的时间复杂度内搜索这个矩阵中的数字?
我在面试中被问到了这个问题,但是我无法想出方法。很好奇是否有解决办法。
我有一个 x
乘以 y
的矩阵,其中每行和每列都按如下升序排列。
1 5 7 9
4 6 10 15
8 11 12 19
14 16 18 21
如何在O(x+y)的时间复杂度内搜索这个矩阵中的数字?
我在面试中被问到了这个问题,但是我无法想出方法。很好奇是否有解决办法。
从第一行的最后一个元素(右上角)开始。
将其与key
进行比较。我们有3种情况:
如果它们相等,则完成搜索。
如果key
大于该元素,则说明key
不能出现在该行中,因此向下移动搜索到下一个元素。
如果key
小于该元素,则说明key
可能出现在该行靠左的位置,但不能出现在更接近下面的列中,因此向左移动搜索到下一个元素。
继续这样做,直到找到该元素或无法继续移动(即不存在该键)。
伪代码:
Let R be number of rows
Let C be number of columns
Let i = 0
Let j = C-1
found = false
while( i>=0 && i<R) && (j>=0 && j<C) )
if (matrix[i][j] == key )
found = true
break
else if( matrix[i][j] > key )
j--
else if( matrix[i][j] < key )
i++
end-while
9
开始。11
> 9
,所以向下移动。11
< 15
向左移动。11
> 10
向下移动。11
< 12
向左移动。11
== 11
- codaddict// the matrix is like this, from left to right is ascending, and
// from down to up is ascending, but the second row'start is not always bigger than the first row's end, which is diff from [leetcode]https://oj.leetcode.com/problems/search-a-2d-matrix/
// 1 5 7 9
// 4 6 10 15
// 8 11 12 19
// 14 16 18 21
// time complexity is O(x+y), x is the count of row, and y is the count of column
public boolean searchMatrix2(int[][] matrix, int target) {
int rowCount = matrix.length;
if(rowCount == 0) return false;
int colCount = matrix[0].length;
if(colCount == 0) return false;
//first find the target row, needs O(x)
int targetRow = 0;
while(targetRow < rowCount-1 && matrix[targetRow+1][0] <= target) {
targetRow++;
}
//than find the target in the target row, needs O(y), so the total is O(x)+O(y)
boolean result = false;
for(int i = 0; i < colCount; i ++) {
if(matrix[targetRow][i] == target) {
result = true;
break;
}
}
return result;
}