设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

Search a 2D Matrix -- LeetCode

2014-04-21 02:29:00.0 LeetCode leetcode java 面试 二分查找 矩阵  
导读:原题链接: http://oj.leetcode.com/problems/search-a-2d-matrix/ 这道题是二分查找Search Insert Position的题目,因为矩阵是行有序并且列有序,查找只需要先按行查找,定位出在哪一行之后再进行列查找即可,所以就是进行两次二分查找。时间复杂度是O(logm+logn),空间上只需两个辅助变量,因而是O(1),代码如下:public b...。。。
原题链接: http://oj.leetcode.com/problems/search-a-2d-matrix/ 
这道题是二分查找Search Insert Position的题目,因为矩阵是行有序并且列有序,查找只需要先按行查找,定位出在哪一行之后再进行列查找即可,所以就是进行两次二分查找。时间复杂度是O(logm+logn),空间上只需两个辅助变量,因而是O(1),代码如下:
public boolean searchMatrix(int[][] matrix, int target) {    if(matrix == null || matrix.length==0 || matrix[0].length==0)        return false;    int l = 0;    int r = matrix.length-1;    while(l<=r)    {        int mid = (l+r)/2;        if(matrix[mid][0] == target) return true;        if(matrix[mid][0] > target)        {            r = mid-1;        }        else        {            l = mid+1;        }    }    int row = r;    if(row<0)        return false;    l = 0;    r = matrix[0].length-1;    while(l<=r)    {        int mid = (l+r)/2;        if(matrix[row][mid] == target) return true;        if(matrix[row][mid] > target)        {            r = mid-1;        }        else        {            l = mid+1;        }    }       return false;}
二分查找是面试中出现频率不低的问题,但是很少直接考二分查找,会考一些变体,除了这道题,还有Search in Rotated Sorted ArraySearch for a Range,思路其实差不多,稍微变化一下即可,有兴趣可以练习一下哈。

(编辑: linhuanmars)

网友评论