Search a 2D Matrix II

Question

Problem Statement

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. [1, 3, 5, 7],
  2. [2, 4, 7, 8],
  3. [3, 5, 9, 10]

Given target = 3, return 2.

Challenge

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

题解 - 自右上而左下

  1. 复杂度要求——O(m+n) time and O(1) extra space，同时输入只满足自顶向下和自左向右的升序，行与行之间不再有递增关系，与上题有较大区别。时间复杂度为线性要求，因此可从元素排列特点出发，从一端走向另一端无论如何都需要m+n步，因此可分析对角线元素。
  2. 首先分析如果从左上角开始搜索，由于元素升序为自左向右和自上而下，因此如果target大于当前搜索元素时还有两个方向需要搜索，不太合适。
  3. 如果从右上角开始搜索，由于左边的元素一定不大于当前元素，而下面的元素一定不小于当前元素，因此每次比较时均可排除一列或者一行元素（大于当前元素则排除当前行，小于当前元素则排除当前列，由矩阵特点可知），可达到题目要求的复杂度。

在遇到之前没有遇到过的复杂题目时，可先使用简单的数据进行测试去帮助发现规律。

Python

  1. class Solution:
  2.     """
  3.     @param matrix: An list of lists of integers
  4.     @param target: An integer you want to search in matrix
  5.     @return: An integer indicates the total occurrence of target in the given matrix
  6.     """
  7.     def searchMatrix(self, matrix, target):
  8.         if not matrix or not matrix[0]:
  9.             return 0
  10.         occur = 0
  11.         row, col = 0, len(matrix[0])-1
  12.         while row < len(matrix) and col >= 0:
  13.             if matrix[row][col] == target:
  14.                 occur += 1
  15.                 col -= 1
  16.             elif matrix[row][col] < target:
  17.                 row += 1
  18.             else:
  19.                 col -= 1
  20.         return occur

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param matrix: A list of lists of integers
  5.      * @param target: An integer you want to search in matrix
  6.      * @return: An integer indicate the total occurrence of target in the given matrix
  7.      */
  8.     int searchMatrix(vector<vector<int> > &matrix, int target) {
  9.         if (matrix.empty() || matrix[0].empty()) {
  10.             return 0;
  11.         }
  13.         const int ROW = matrix.size();
  14.         const int COL = matrix[0].size();
  16.         int row = 0, col = COL - 1;
  17.         int occur = 0;
  18.         while (row < ROW && col >= 0) {
  19.             if (target == matrix[row][col]) {
  20.                 ++occur;
  21.                 --col;
  22.             } else if (target < matrix[row][col]){
  23.                 --col;
  24.             } else {
  25.                 ++row;
  26.             }
  27.         }
  29.         return occur;
  30.     }
  31. };

Java

  1. public class Solution {
  2.     /**
  3.      * @param matrix: A list of lists of integers
  4.      * @param: A number you want to search in the matrix
  5.      * @return: An integer indicate the occurrence of target in the given matrix
  6.      */
  7.     public int searchMatrix(int[][] matrix, int target) {
  8.         int occurrence = 0;
  9.         if (matrix == null || matrix[0] == null) {
  10.             return occurrence;
  11.         }
  13.         int row = 0, col = matrix[0].length - 1;
  14.         while (row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length) {
  15.             if (matrix[row][col] == target) {
  16.                 occurrence++;
  17.                 col--;
  18.             } else if (matrix[row][col] > target) {
  19.                 col--;
  20.             } else {
  21.                 row++;
  22.             }
  23.         }
  25.         return occurrence;
  26.     }
  27. }

源码分析

  1. 首先对输入做异常处理，不仅要考虑到matrix为空串，还要考虑到matrix[0]也为空串。
  2. 注意循环终止条件。
  3. 在找出target后应继续向左搜索其他可能相等的元素，下方比当前元素大，故排除此列。

严格来讲每次取二维矩阵元素前都应该进行 null 检测。

复杂度分析

由于每行每列遍历一次，故时间复杂度为 O(m + n).

Reference

Searching a 2D Sorted Matrix Part II | LeetCode