面试题 10.09

Given an M x N matrix in which each row and each column is sorted in ascending order, write a method to find an element.

Example:

Given matrix:

[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] Given target = 5, return true.

Given target = 20, return false.

Solutions

1. binary search O(m + n)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (!matrix.size()) return false;

        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            int val = matrix[i][j];
            if (target > val)
                i++;
            else if (target < val)
                j--;
            else
                return true;
        }

        return false;
    }
};