#38 Search a 2D Matrix II

题目描述：

Write an efficient algorithm that searches for a value in an m x n matrix, return the occurrence of it.

This matrix has the following properties:

Integers in each row are sorted from left to right.Integers in each column are sorted from up to bottom.No duplicate integers in each row or column. Have you met this question in a real interview?  Yes Example

Consider the following matrix:

[ [1, 3, 5, 7], [2, 4, 7, 8], [3, 5, 9, 10] ]

Given target = 3, return 2.

Challenge 

O(m+n) time and O(1) extra space

题目思路：

这题还是延续了#28搜索两遍的办法，不同的是，target可能在任何符合条件的row中出现。我就用一个vector去存所有符合条件的row，然后把这些row一个一个拿出来做binary search，如果找到target就+1.

Mycode（AC = 44ms）：

class Solution { public: /** * @param matrix: A list of lists of integers * @param target: An integer you want to search in matrix * @return: An integer indicate the total occurrence of target in the given matrix */ int searchMatrix(vector<vector<int> > &matrix, int target) { // write your code here int num_rows = matrix.size(); if (num_rows == 0) return 0; int num_cols = matrix[0].size(); // find all possible rows that target will appear vector<int> target_rows; for (int i = 0; i < num_rows; i++) { if (matrix[i][0] <= target && matrix[i][num_cols - 1] >= target) { target_rows.push_back(i); } } // traverse all the possible rows and find the target // in each row int count = 0; for (int i = 0; i < target_rows.size(); i++) { int row = target_rows[i]; int l = 0, r = num_cols; while (l <= r) { int mid = (l + r) / 2; if (matrix[row][mid] == target) { count++; break; } else if (matrix[row][mid] < target) { l = mid + 1; } else { r = mid - 1; } } } return count; } };