Lexi's Leetcode solutions

这个好像两年前在纽约就做过，到今天才好好分析了一遍。Leetcode上面的这篇分析特别特别好，看过一遍顺便还练习算时间复杂度了。总之两个比较好的解法：

1. O(n)的linear解法：

因为二维矩阵是行列都sort好的，所以最上面一行和最右边一列正好形成了一个sort好的递增数列。取右上角这个A[i][j]，它左边的全<x, 它下边的全>x，所以每次可以删掉一行/列。这样每次往下/往左走一步，最后要是走到左下角了还没找到，那走的最多步数是m + n步。所以时间是O(m + n)。

public boolean searchMatrixLinear(int[][] matrix, int target) {
  int i = 0, j = matrix[0].length - 1;
  while (i < matrix.length && j >= 0) {
    if (matrix[i][j] == target)
      return true;
    else if (matrix[i][j] > target) // eliminate col, go left
      j--;
    else
      i++; // eliminate row, go down
  }
  return false;
}

2. O(logm * logn)的更快的解法：

每次取中间一列，然后在这一列里面binary search，要是没找到，最后会找到(j1, j2)这样的两个位置，A[i][j1] < x && A[i][j2]。说明(i, j1)左上的全<x，(i, j 2)右下的全>x，说明x肯定不在这两块里面，就可以eliminate掉了。在剩下的两块里面各自找x，然后返回||。

这个时间复杂度为什么是O(logm * logn)？每次删掉行数的一半，是logm，在每个check的row里面做一次binary search是logn。

public boolean searchMatrixFastest(int[][] matrix, int target) {
  return searchBinary(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, target);
}
private boolean searchBinary(int[][] matrix, int i1, int i2, int j1, int j2, int x) {
  if (i1 > i2 || j1 > j2)
    return false;
  int midRow = (i1 + i2) / 2; 
  int midCol = searchInRow(matrix, midRow, j1, j2, x); 
  if (midCol == -10) //用-10不用-1因为可能没找到但是q=-1
    return true;
  return searchBinary(matrix, i1, midRow - 1, midCol + 1, j2, x) || searchBinary(matrix, midRow + 1, i2, j1, midCol, x);
}
private int searchInRow(int[][] matrix, int i, int p, int q, int x) {
  while (p <= q) {
    int mid = (p + q) / 2;
    if (matrix[i][mid] == x)
      return -10;
    else if (matrix[i][mid] > x) // go up
      q = mid - 1;
    else
      p = mid + 1;
  }
  return q;
}