240. Search a 2D Matrix II

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/search-a-2d-matrix-ii/description/

想法

对角线延伸？

最直觉的是，扫一行，找到特定行再扫列
不，并不对

对角线！

二分查找：
0, 1, 2, 3, 4, 5

看别人解答吧，感觉思路不够明确

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size();
        int n = matrix[0].size();
        
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target)
                return true;
            if (matrix[i][j] > target)
                j--;
            else
                i++;
        }
        return false;
    }
};

回顾

这算是一个经典的trick吧

还是自己没能发现其中的性质
把向两边扩展转化为只向一边扩展，这真的很关键！！！

记住它吧！