# Search a 2D Matrix II ### Source - leetcode: [Search a 2D Matrix II | LeetCode OJ](https://leetcode.com/problems/search-a-2d-matrix-ii/) - lintcode: [(38) Search a 2D Matrix II](http://lintcode.com/en/problem/search-a-2d-matrix-ii/) ### Problem 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 ### 題解 - 自右上而左下 1. 復雜度要求——O(m+n) time and O(1) extra space，同時輸入只滿足自頂向下和自左向右的升序，行與行之間不再有遞增關系，與上題有較大區別。時間復雜度為線性要求，因此可從元素排列特點出發，從一端走向另一端無論如何都需要m+n步，因此可分析對角線元素。 1. 首先分析如果從左上角開始搜索，由于元素升序為自左向右和自上而下，因此如果target大于當前搜索元素時還有兩個方向需要搜索，不太合適。 1. 如果從右上角開始搜索，由于左邊的元素一定不大于當前元素，而下面的元素一定不小于當前元素，因此每次比較時均可排除一列或者一行元素（大于當前元素則排除當前行，小于當前元素則排除當前列，由矩陣特點可知），可達到題目要求的復雜度。 **在遇到之前沒有遇到過的復雜題目時，可先使用簡單的數據進行測試去幫助發現規律。** ### C++ ~~~ 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) { if (matrix.empty() || matrix[0].empty()) { return 0; } const int ROW = matrix.size(); const int COL = matrix[0].size(); int row = 0, col = COL - 1; int occur = 0; while (row < ROW && col >= 0) { if (target == matrix[row][col]) { ++occur; --col; } else if (target < matrix[row][col]){ --col; } else { ++row; } } return occur; } }; ~~~ ### Java ~~~ public class Solution { /** * @param matrix: A list of lists of integers * @param: A number you want to search in the matrix * @return: An integer indicate the occurrence of target in the given matrix */ public int searchMatrix(int[][] matrix, int target) { int occurrence = 0; if (matrix == null || matrix[0] == null) { return occurrence; } int row = 0, col = matrix[0].length - 1; while (row >= 0 && row < matrix.length && col >= 0 && col < matrix[0].length) { if (matrix[row][col] == target) { occurrence++; col--; } else if (matrix[row][col] > target) { col--; } else { row++; } } return occurrence; } } ~~~ ### 源碼分析 1. 首先對輸入做異常處理，不僅要考慮到matrix為空串，還要考慮到matrix[0]也為空串。 1. 注意循環終止條件。 1. 在找出`target`后應繼續向左搜索其他可能相等的元素，下方比當前元素大，故排除此列。 **嚴格來講每次取二維矩陣元素前都應該進行 null 檢測。** ### 復雜度分析 由于每行每列遍歷一次，故時間復雜度為 O(m+n)O(m + n)O(m+n). ### Reference [Searching a 2D Sorted Matrix Part II | LeetCode](http://articles.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html)