LeetCode 240. 搜索二维矩阵 II

朱雀 2022-10-25 13:00 126阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]

//写法一：逐行二分  可提前判断是否有解
    class Solution {
        
        public boolean searchMatrix(int[][] matrix, int target) {
        
            for(int i = 0; i < matrix.length; i++){
        
                if(matrix[i][0] > target)
                    break;
                if(matrix[i][matrix[i].length - 1] < target)
                    continue;
                if(bsearch(matrix[i], target))
                    return true;
            }
            return false;
        }
    
        private boolean bsearch(int[] nums, int target){
        
            int l = 0;
            int r = nums.length - 1;
            while(l < r){
        
                int mid = l + r + 1 >> 1;
                if(nums[mid] <= target)
                    l = mid;
                else
                    r = mid - 1;
            }
            return nums[l] == target;
        }
    }

//解法二：在对角线方向移动 分别二分竖向和横向但是效果并不比解法一好
    class Solution {
        
        private boolean bsearch(int[][] arr, int start, int target){
        
            
            int l = start;
            int r = arr.length - 1;
            //竖向
            while(l < r){
        
                int mid = l + r + 1>> 1;
                if(arr[mid][start] <= target)
                    l = mid;
                else
                    r = mid - 1;
            }
            if(arr[l][start] == target)
                return true;
            
            l = start;
            r = arr[0].length - 1;
            //横向
            while(l < r){
        
                int mid = l + r + 1 >> 1;
                if(arr[start][mid] <= target)
                    l = mid;
                else
                    r = mid - 1;
            }
            return arr[start][l] == target;
        }
    
        public boolean searchMatrix(int[][] matrix, int target) {
        
            int m = matrix.length;
            int n = matrix[0].length;
            int shortnum = Math.min(m, n);
            for(int i = 0; i < shortnum; i++){
        
                if(bsearch(matrix, i, target))
                    return true;
            }
            return false;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/cc6147510fad419c982c2902c0f60525.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70 1]: /images/20221024/44119b5bece7448fbd92774294e6dda2.png