[LeetCode] Search a 2D Matrix - c++编程基础

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.

问题描述：在一个m*n的矩阵中查找一个值，算法尽量高效。

矩阵满足下列特征：

1、每行的整数从左到右排序

2、一行的第一个整数大于前一行的最后一个整数

思路是将要查找的整数与每行的最后一个整数比较，如果大于的话，往后遍历，如果小于就停止，之后再对停止时的vector遍历即可。

class Solution {  
public:  
    bool searchMatrix(vector > &matrix, int target) {  
        // Note: The Solution object is instantiated only once and is reused by each test case.  
        vector ivec;  
        for(vector >::iterator iter = matrix.begin();  
                                           iter != matrix.end(); ++iter) {  
            ivec = *iter;  
            if(target <= ivec[ivec.size()-1])  
                break;  
        }  
  
        for(vector::iterator iter = ivec.begin();  
                                  iter != ivec.end(); ++iter) {  
            if(target == *iter)  
                return true;  
        }  
  
        return false;  
    }  
};