Search a 2D Matrix II

Description

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.

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

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

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
        if (matrix.empty()) {
            return 0;
        }
        int result = 0;
        int rowlength  = matrix[0].size();
        for (int i = 0; i < matrix.size(); ++i) {
            int start = 0;
            int end = rowlength-1;
            // exceeding current row
            if (target < matrix[i][start]) {
              continue;
            } else if (target > matrix[i][end]) {
              continue;
            }
            // binary search for current row
            while (start+1 < end) {
                int mid = start + (end - start) / 2;
                if (target == matrix[i][mid]) {
                    result++;
                    break;
                } else if (target < matrix[i][mid]) {
                    end = mid;
                } else {
                    start = mid;
                }
            }
            if (target == matrix[i][start]) {
                result++;
            } else if (target == matrix[i][end]) {
                result++;
            }
        }
        return result;
    }
};

Similar problems

x

Tags

x