leetcode_search_a_2d_mamtrix

发表于

难度：Medium
解题思路：对于一个二维数组，从最后一排，从左到右的搜索，如遇到比targe大的元素，则停止该排搜索，跳到上一排，以此类推。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        auto first_level_reverse_it = matrix.rbegin();
        auto first_level_reverse_begin_it = matrix.rbegin();
        auto first_level_reverse_end_it = matrix.rend();
        for(;first_level_reverse_it != first_level_reverse_end_it;first_level_reverse_it++)
        {
            auto second_level_it = (*first_level_reverse_it).begin();
            auto second_level_begin_it = (*first_level_reverse_it).begin();
            auto second_level_end_it = (*first_level_reverse_it).end();
            for(;second_level_it != second_level_end_it;second_level_it++)
            {
                if(*second_level_it == target)
                    return true;
                else if(*second_level_it > target)
                    break;
            }
        }
        return false;
    }
};

代码结果：运行时间8ms，超过43.19%。

另一种思路：使用两次二分查找，第一次找出应该搜索的行，第二次在改行搜索。

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
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty())
            return false;
        int m = matrix.size();
        int n = matrix[0].size();
        if(target < matrix[0][0] || target > matrix[m-1][n-1])
            return false;
        int low = 0;
        int high = m-1;
        while(low <= high)
        {
            // cout<<"low:"<<low<<endl;
            // cout<<"high:"<<high<<endl;
            int mid = low + (high-low)/2;
            if(matrix[mid][0] == target)
                return true;
            else if(matrix[mid][0] > target)
                high = mid-1;
            else 
                low = mid+1;
        }
        // cout<<"low: "<<low<<endl;
        int row = low-1;	//此时low为target应该插入的位置，则target > matrix[low][0] 且 target < matrix[low-1][0]。所以应该在low-1行搜索。
        low = 0;
        high = n-1;
        while(low <= high)
        {
            int mid  = low + (high-low)/2;
            if(matrix[row][mid] == target)
                return true;
            else if(matrix[row][mid] > target)
                high = mid-1;
            else if(matrix[row][mid] < target)
                low = mid+1;
        }
        return false;
    }
};

运行结果：13ms，超过16.16%。

二分查找：https://yeepom.github.io/2016/12/04/iterative-binary-search/