最近我遇到了这样一道面试题，我想知道一个好的解决方法。
假设有一个二维数组，数组中的所有数字从左到右、从上到下递增。
最好的方法是什么来搜索和确定目标数字是否在数组中？
现在，我的第一反应是利用二分搜索，因为我的数据已经排序。我可以在O(log N)时间内确定单行中是否存在数字。但是，两个方向上的情况让我摸不着头脑。
另一个我认为可能有效的解决方法是从中间某个位置开始。如果中间的值小于我的目标值，那么我可以确定它在矩阵的左侧部分。然后我斜着移动并再次检查，缩小目标数字可能所在的正方形区域的大小，直到我锁定目标数字。
请问有没有人对解决这个问题有好的想法？
示例数组：
从左到右，从上到下排序。
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
这里有一个简单的方法：
对于一个NxM数组，它的运行时间为O（N+M）。我认为很难做得更好。 :)
编辑：有很多好的讨论。我上面说的是一般情况；显然，如果N或M很小，你可以使用二分搜索方法在接近对数时间内完成此操作。
以下是一些细节，供那些好奇的人参考：
这个简单的算法称为Saddleback Search。它已经存在一段时间了，并且当N == M时是最优的。一些参考资料：
然而，当N < M时，直觉表明二分搜索应该比O(N+M)更好：例如，当N == 1时，纯二分搜索将以对数而不是线性时间运行。
Richard Bird在2006年的一篇论文中研究了这种二分搜索可以改进Saddleback算法的直觉：
Bird使用一种非常不寻常的对话技巧向我们展示了当N <= M时，该问题具有下限Ω(N * log(M/N))。这个下限很有意义，因为它在N == M时给出了线性性能，在N == 1时给出了对数性能。
一种使用逐行二分查找的方法如下所示：
N < M。假设 N 是行数，M 是列数。value 进行二分查找。如果我们找到了它，就完成了。s 和 g，其中 s < value < g。value，因此我们可以将其消除。value，因此我们可以将其消除。就最坏情况而言，该算法需要进行 log(M) 的工作来消除一半可能的解，并在两个较小的问题上递归地调用自身两次。我们必须为每一行重复一个较小版本的 log(M) 的工作，但是如果行数与列数相比较小，则能够在对数时间内消除所有这些列变得更加值得。
这使得该算法的复杂度为 T(N,M) = log(M) + 2 * T(M/2, N/2)，Bird 表明它是 O(N * log(M/N))。
Craig Gidney提出的另一种方法描述了一种类似于上述方法的算法：它使用M/N的步长逐行检查。他的分析表明，这也会导致O(N * log(M/N))的性能。
大O分析很好，但这些方法在实践中表现如何呢？下面的图表检查了四种算法，针对越来越“方形”的数组：
“朴素”算法只是搜索数组的每个元素。“递归”算法如上所述。“混合”算法是Gidney's algorithm的一种实现。对于每个数组大小，通过在固定的1,000,000个随机生成的数组集合上计时每个算法来衡量性能。
一些值得注意的点：
巧妙地使用二分查找可以为矩形和正方形数组提供O(N * log(M/N)的性能。 O(N + M)的“Saddleback”算法更简单，但随着数组变得越来越矩形化，性能会下降。
M==N 时，我们希望复杂度为 O(N)，而不是 O(N*log(N/N))，因为后者为零。当 N<=M 时，正确的“统一”尖锐边界是 O(N*(log(M/N)+1))。 - hardmathΘ(b lg(t)) 的时间，其中 b=min(w,h)，t=b/max(w,h)。我在这篇博客文章中讨论了解决方案。
下限
通过将自身限制在主对角线上，对手可以迫使算法进行 Ω(b lg(t)) 个查询：Ω(b lg(t)) 个查询才能完全消除它们。
算法
w >= h）t进行比较
t个单元格。如果在执行此操作时找到匹配项，则返回其位置。t个短列。查找项目：
确定项目不存在：
图例：白色单元格是较小的项，灰色单元格是较大的项，绿色单元格是相等的项。
分析 需要消除 b*t 个短列。需要消除 b 个长行。消除长行的成本为O(lg(t))时间。消除t个短列的成本为O(1)时间。O(lg(t)*b + b*t*1/t) = O(b lg(t))。lg将结果夹紧到大于1的值（即lg(x) = log_2(max(2,x))）。这就是当w=h时，意味着t=1，我们得到了期望的上限O(b lg(1)) = O(b) = O(w+h)的原因。
代码
public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
if (grid == null) throw new ArgumentNullException("grid");
comparer = comparer ?? Comparer<T>.Default;
// check size
var width = grid.Count;
if (width == 0) return null;
var height = grid[0].Count;
if (height < width) {
var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
if (result == null) return null;
return Tuple.Create(result.Item2, result.Item1);
}
// search
var minCol = 0;
var maxRow = height - 1;
var t = height / width;
while (minCol < width && maxRow >= 0) {
// query the item in the minimum column, t above the maximum row
var luckyRow = Math.Max(maxRow - t, 0);
var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);
// did we eliminate t rows from the bottom?
if (cmpItemVsLucky < 0) {
maxRow = luckyRow - 1;
continue;
}
// we eliminated most of the current minimum column
// spend lg(t) time eliminating rest of column
var minRowInCol = luckyRow + 1;
var maxRowInCol = maxRow;
while (minRowInCol <= maxRowInCol) {
var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
if (cmpItemVsMid > 0) {
minRowInCol = mid + 1;
} else {
maxRowInCol = mid - 1;
maxRow = mid - 1;
}
}
minCol += 1;
}
return null;
}
O(b*(lg(t)+1))，而不是O(b*lg(t))。很好的写作，特别是要注意在展示“最坏情况”限制时使用"对手技术"。 - hardmathbool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)
if (minX == maxX and minY == maxY and arr[minX,minY] != value)
return false
if (arr[minX,minY] > value) return false; // Early exits if the value can't be in
if (arr[maxX,maxY] < value) return false; // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
print nextX,nextY
return true
}
else if (arr[nextX,nextY] < value)
{
if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
return true
return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
return true
reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}
public class SearchSortedArray2D {
static boolean findZigZag(int[][] a, int t) {
int i = 0;
int j = a.length - 1;
while (i <= a.length - 1 && j >= 0) {
if (a[i][j] == t) return true;
else if (a[i][j] < t) i++;
else j--;
}
return false;
}
static boolean findBinarySearch(int[][] a, int t) {
return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
}
static boolean findBinarySearch(int[][] a, int t,
int r1, int c1, int r2, int c2) {
if (r1 > r2 || c1 > c2) return false;
if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
if (a[r1][c1] > t) return false;
if (a[r2][c2] < t) return false;
int rm = (r1 + r2) / 2;
int cm = (c1 + c2) / 2;
if (a[rm][cm] == t) return true;
else if (a[rm][cm] > t) {
boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
return (b1 || b2);
} else {
boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
return (b1 || b2);
}
}
static void randomizeArray(int[][] a, int N) {
int ri = (int) (Math.random() * N);
int rj = (int) (Math.random() * N);
a[ri][rj] = 2;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == ri && j == rj) continue;
else if (i > ri || j > rj) a[i][j] = 3;
else a[i][j] = 1;
}
}
}
public static void main(String[] args) {
int N = 8000;
int[][] a = new int[N][N];
int randoms = 100;
int repeats = 1000;
long start, end, duration;
long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
long zigSum = 0, zigAvg;
long binSum = 0, binAvg;
for (int k = 0; k < randoms; k++) {
randomizeArray(a, N);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findZigZag(a, 2);
end = System.currentTimeMillis();
duration = end - start;
zigSum += duration;
zigMin = Math.min(zigMin, duration);
zigMax = Math.max(zigMax, duration);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
end = System.currentTimeMillis();
duration = end - start;
binSum += duration;
binMin = Math.min(binMin, duration);
binMax = Math.max(binMax, duration);
}
zigAvg = zigSum / randoms;
binAvg = binSum / randoms;
System.out.println(findZigZag(a, 2) ?
"Found via zigzag method. " : "ERROR. ");
//System.out.println("min search time: " + zigMin + "ms");
System.out.println("max search time: " + zigMax + "ms");
System.out.println("avg search time: " + zigAvg + "ms");
System.out.println();
System.out.println(findBinarySearch(a, 2) ?
"Found via binary search method. " : "ERROR. ");
//System.out.println("min search time: " + binMin + "ms");
System.out.println("max search time: " + binMax + "ms");
System.out.println("avg search time: " + binAvg + "ms");
}
}
这是一个关于该问题下限的简短证明。
你不能比线性时间更好地完成它（以数组维度而非元素数量为单位）。在下面的数组中，标记为*的每个元素都可以是5或6（与其他元素无关）。因此，如果您的目标值是6（或5），算法需要检查所有这些元素。
1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10
bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;
int xnew = (xmin + xmax)/2;
int ynew = (ymin + ymax)/2;
if (arr[xnew][ynew] == key) return true;
if (arr[xnew][ynew] < key)
{
if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
} else {
if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
}
}
findNum() 应该被记录文档，至少需要说明“最大值”是否包含在内。我认为这里存在一些偏差错误：如果目标位于 xnew 或 ynew 中的任意一个，但不在 [xnew][ynew] 中怎么办？ - greybeard现在我问，两个边界之间有什么吗？如果有，那一定是3。如果没有，那就没有3。这种方式有点间接，因为我实际上并没有找到这个数字，我只是推断它必须在那里。这还有一个额外的好处，就是可以计算所有的3。
我在一些例子上尝试了一下，似乎效果还不错。
通过数组的对角线进行二分查找是最佳选择。 我们可以找出元素是否小于或等于对角线上的元素。
import Cocoa
class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
if (matrix.isEmpty || matrix[0].isEmpty) {
return false
}
return _searchMatrix(matrix, 0..<matrix.count, 0..<matrix[0].count, target)
}
func _searchMatrix(_ matrix: [[Int]], _ rows: Range<Int>, _ columns: Range<Int>, _ target: Int) -> Bool {
if (rows.count == 0 || columns.count == 0) {
return false
}
if (rows.count == 1) {
return _binarySearch(matrix, rows.lowerBound, columns, target, true)
}
if (columns.count == 1) {
return _binarySearch(matrix, columns.lowerBound, rows, target, false)
}
var lowerInflection = (-1, -1)
var upperInflection = (Int.max, Int.max)
var currentRows = rows
var currentColumns = columns
while (currentRows.count > 0 && currentColumns.count > 0 && upperInflection.0 > lowerInflection.0+1) {
let rowMidpoint = (currentRows.upperBound + currentRows.lowerBound) / 2
let columnMidpoint = (currentColumns.upperBound + currentColumns.lowerBound) / 2
let value = matrix[rowMidpoint][columnMidpoint]
if (value == target) {
return true
}
if (value > target) {
upperInflection = (rowMidpoint, columnMidpoint)
currentRows = currentRows.lowerBound..<rowMidpoint
currentColumns = currentColumns.lowerBound..<columnMidpoint
} else {
lowerInflection = (rowMidpoint, columnMidpoint)
currentRows = rowMidpoint+1..<currentRows.upperBound
currentColumns = columnMidpoint+1..<currentColumns.upperBound
}
}
if (lowerInflection.0 == -1) {
lowerInflection = (upperInflection.0-1, upperInflection.1-1)
} else if (upperInflection.0 == Int.max) {
upperInflection = (lowerInflection.0+1, lowerInflection.1+1)
}
return _searchMatrix(matrix, rows.lowerBound..<lowerInflection.0+1, upperInflection.1..<columns.upperBound, target) || _searchMatrix(matrix, upperInflection.0..<rows.upperBound, columns.lowerBound..<lowerInflection.1+1, target)
}
func _binarySearch(_ matrix: [[Int]], _ rowOrColumn: Int, _ range: Range<Int>, _ target: Int, _ searchRow : Bool) -> Bool {
if (range.isEmpty) {
return false
}
let midpoint = (range.upperBound + range.lowerBound) / 2
let value = (searchRow ? matrix[rowOrColumn][midpoint] : matrix[midpoint][rowOrColumn])
if (value == target) {
return true
}
if (value > target) {
return _binarySearch(matrix, rowOrColumn, range.lowerBound..<midpoint, target, searchRow)
} else {
return _binarySearch(matrix, rowOrColumn, midpoint+1..<range.upperBound, target, searchRow)
}
}
}
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null)
return false;
int i=0;
int j=0;
int m = matrix.length;
int n = matrix[0].length;
boolean found = false;
while(i<m && !found){
while(j<n && !found){
if(matrix[i][j] == target)
found = true;
if(matrix[i][j] < target)
j++;
else
break;
}
i++;
j=0;
}
return found;
}}
通过了 129 / 129 个测试用例。
状态: 已接受
运行时间: 39 毫秒
内存使用: 55 MB