074.Searcha2DMatrix.md

74. Search a 2D Matrix

Question:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row.

Example:

Input:Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

Analysis:

首先在行的首字母元素里面判断Interger应该放在哪个位置

然后在列里面判断这个Interger应该插入到哪个位置

O(m+n)的时间复杂度

另一个想法：我们从第0行的最右端开始搜索，两种情况：

1. 如果当前的数比target大，则说明target必然在target的左边，则搜索其左边的位置

2. 如果当前的数比target小，则说明和target相等的数必然不在这一行，因此往下一行搜索。

3. 如果当前的数和target相等，则说明找到了这个target

O(m+n)的时间复杂度

另一想法：二分法来找数字在哪行哪列 O(lgm + lgn)时间复杂度

Solution1:

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if matrix == [[]] or matrix == []:
            return False
        count = 0
        for i in range(len(matrix)):
            if target == matrix[i][0]:
                return True
            if target < matrix[i][0]:
                count = 1
                break
        if count == 0:
            i = i
        else:        
            i = i - 1
        count = 0

        for j in range(len(matrix[0])):
            if target == matrix[i][j]:
                count = 1
                return True
        if count == 0:
            return False

Solution2:

class Solution {  
public:  
    bool searchMatrix(vector<vector<int>>& matrix, int target) {  
    	int m = (int)matrix.size();
        if (!m) return false;
        int i = 0, j = matrix[0].size() -1;  
        while(i < matrix.size() && j >= 0)  
        {  
            if(matrix[i][j] == target) return true;  
            else if(matrix[i][j] > target) j--;  
            else if(matrix[i][j] < target) i++;  
        }  
        return false;  
    }  
};  

Solution3:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = (int)matrix.size();
        if (!m) return false;
        int n = (int)matrix[0].size();        
        int lo, hi;
        for (lo = 0, hi = m*n; hi-lo > 1;) {
            int mid = (lo+hi) >> 1;
            if (matrix[mid/n][mid%n] > target) hi = mid;
            else lo = mid;
        }
        return (hi-lo == 1) && (matrix[lo/n][lo%n] == target);
    }
};

Keypoint:

二分法：不要看做一个矩阵，而是看做一个List,对整个list用二分法 O(logM+logN) 看做矩阵：往下找数的时候，右移，或者下移 O(M+N)