Lexi's Leetcode solutions

[leetcode] Search a 2D Matrix | 二维矩阵找其中某个element的位置

Posted on: October 13, 2013

这个好像两年前在纽约就做过,到今天才好好分析了一遍。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;
}

 

 

Advertisements

3 Responses to "[leetcode] Search a 2D Matrix | 二维矩阵找其中某个element的位置"

Lexi姐姐这个第二个算法时间复杂是不是应该是O(logn + logm),或者O(log(n*m))?

这道题应该把整个matrix看成一个一个sorted array,长度m*n, 这样做binary search应该会比lz的方法时间消耗更小 时间复杂度为O(log(m*n))

A[i][j1] < x && A[i][j2]笔误吧
应该不是&&是<

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: