LeetCode 74 Search a 2D Matrix（搜索2D矩陣）

LeetCode 74 Search a 2D Matrix（搜索2D矩陣）

翻譯

寫一個高效算法用於在一個m x n的矩陣中查找一個值。
這個矩陣有如下屬性：

每行的整型數都是從左到右排序的。
每行的第一個元素都比上一行的最後一列大。

例如，
考慮如下矩陣：
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
給定target = 3，返回true。

原文

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.
For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

分析

可能因為我好困了，所以不論是算法還是我自己，都效率很低……

下面這個代碼也是一改再改……

bool searchMatrix(vector>& matrix, int target) {
    if (matrix[0][0] > target) return false;
    for (int i = 0; i < matrix.size(); ) {
        for (int j = 0; j < matrix[i].size(); ) {
            if (i == matrix.size() - 1 && matrix[i][j] < target) {
                if (j >= matrix[i].size()) return false;
                j += 1;
                if (matrix[i][j] > target) return false;
            }
            else if (matrix[i][j] < target && matrix[i+1][j] > target) {
                j += 1;
                if (j >= matrix[i].size()) return false;
                if (matrix[i][j] > target) return false;
            }
            else if (matrix[i][j] < target && matrix[i + 1][j] <= target) {
                i += 1;
            }
            else if (matrix[i][j] == target) {
                return true;
            }     
            if (i == matrix.size() - 1 && j == matrix[i].size() ) {
                return false;
            }
        }
    }
    return false;
}

明天再整理整理思路重新做一遍吧……