74. Search a 2D Matrix

发表于 | 分类于

每日一题 2019 - 04 - 09

题目：

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 1:

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

Example 2:

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

解法：

这个题让在给定的矩阵中查找元素，矩阵每一行的元素已经从小到大排列完毕，基于这个特性就很好解决问题了，思路就是先定位到该元素应该在那一行，因为所有行的元素都是有序的，所以只要这个元素大小位于某一行的首元素和尾元素之间，那么这个元素可能在这一行；随后在这一行中使用二分查找就可以降低时间复杂度到 O(logn) 成功解决问题了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if( matrix.size() == 0  || matrix[0].size() == 0  )
        {
            return false ;
        }
        int length = matrix.size() ;
        int width = matrix[0].size() ;
        for(int i = 0 ; i < length ; i ++ )
        {
            if( matrix[i][0] <= target && matrix[i][width - 1] >= target )
            {
                if(matrix[i][0] == target)
                {
                    return true ;
                }
                if(matrix[i][width -1] == target)
                {
                    return true ;
                }
                int left = 0 ; 
                int right = width - 1  ;
                while( left <= right )
                {
                    int mid = ( left + right ) / 2 ;
                    
                    if( matrix[i][mid] > target )
                    {
                        right = mid - 1 ;
                    }
                    else if(matrix[i][mid] < target)
                    {
                        left = mid + 1 ;
                    }
                    else
                    {
                        return true ;
                    }
                }
            }
            else
            {
                continue ;
            }
        }
        return false ;
    }
};
0%
undefined