首页 > 代码库 > LintCode-Search 2D Matrix II
LintCode-Search 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.
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
Solution: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(ArrayList<ArrayList<Integer>> matrix, int target) { 8 int m = matrix.size(); 9 if (m==0) return 0;10 int n = matrix.get(0).size();11 if (n==0) return 0;12 13 return searchMatrixRecur(matrix,target,0,0,m-1,n-1);14 }15 16 public int searchMatrixRecur(ArrayList<ArrayList<Integer>> matrix, int target, int x1, int y1, int x2, int y2){17 if (x2<x1 || y2<y1) return 0;18 19 if (x1==x2 && y1==y2)20 if (matrix.get(x1).get(y1)==target) return 1;21 else return 0;22 23 int midX = (x1+x2)/2;24 int midY = (y1+y2)/2;25 int midVal = matrix.get(midX).get(midY);26 int res = 0;27 28 if (midVal==target){29 //We have to search all the four sub matrix.30 res++;31 res += searchMatrixRecur(matrix,target,x1,y1,midX-1,midY-1);32 res += searchMatrixRecur(matrix,target,midX+1,midY+1,x2,y2);33 res += searchMatrixRecur(matrix,target,(x1+x2)/2+1,y1,x2,(y1+y2)/2-1);34 res += searchMatrixRecur(matrix,target,x1,(y1+y2)/2+1,(x1+x2)/2-1,y2);35 } else if (midVal>target) {36 int leftX = (x1+x2)/2;37 int leftY = y1;38 int upX = x1;39 int upY = (y1+y2)/2;40 if (target==matrix.get(leftX).get(leftY)) res++;41 if (target==matrix.get(upX).get(upY)) res++;42 if (target <= matrix.get(leftX).get(leftY) && target <=matrix.get(upX).get(upY)){43 res += searchMatrixRecur(matrix,target,x1,y1,midX-1,midY-1);44 } else if (target <= matrix.get(leftX).get(leftY)){45 res += searchMatrixRecur(matrix,target,x1,y1,(x1+x2)/2-1,y2);46 } else if (target <= matrix.get(upX).get(upY)){47 res += searchMatrixRecur(matrix,target,x1,y1,x2,(y1+y2)/2-1);48 } else {49 res += searchMatrixRecur(matrix,target,x1,y1,x2,(y1+y2)/2-1);50 res += searchMatrixRecur(matrix,target,upX,upY,(x1+x2)/2-1,y2);51 }52 } else {53 int rightX = (x1+x2)/2;54 int rightY = y2;55 int lowX = x2;56 int lowY = (y1+y2)/2;57 if (target==matrix.get(rightX).get(rightY)) res++;58 if (target==matrix.get(lowX).get(lowY)) res++;59 if (target >= matrix.get(rightX).get(rightY) && target >= matrix.get(lowX).get(lowY)){60 res += searchMatrixRecur(matrix,target,midX+1,midY+1,x2,y2);61 } else if (target >= matrix.get(rightX).get(rightY)){62 res += searchMatrixRecur(matrix,target, (x1+x2)/2+1,y1,x2,y2);63 } else if (target >= matrix.get(lowX).get(lowY)){64 res += searchMatrixRecur(matrix,target, x1, (y1+y2)/2+1, x2, y2);65 } else {66 res += searchMatrixRecur(matrix,target, (x1+x2)/2+1,y1, lowX, lowY);67 res += searchMatrixRecur(matrix,target, x1, (y1+y2)/2+1, x2, y2);68 }69 70 }71 return res;72 }73 }
LintCode-Search 2D Matrix II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。