LeetCode每日一题

LeetCode每日一题:剑指 Offer 04. 二维数组中的

2020-08-12  本文已影响0人  Patarw

第一种解法:
因为是递增的数列,所以左边肯定是最小值,右边肯定是最大值,所以只需要拿目标数与每一行的左右比较看其是否在左右两数之间,在的话就用二分查找找出目标值。

 class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
    if(matrix.length == 0 || matrix[0].length == 0){
        return false;
    }
    for(int i = 0;i < matrix.length;i++){
       
        if(target >= matrix[i][0] && target <= matrix[i][matrix[i].length - 1]){
            int left = 0;
            int right = matrix[i].length - 1;
            int mid = 0;
            while(left <= right){
                mid = (left + right) / 2;
                if(target < matrix[i][mid]){
                    right = mid - 1;
                } else if(target > matrix[i][mid]){
                    left = mid + 1;
                }else if(target == matrix[i][mid]){
                    return true;
                }
            }
        }
    }
    return false;
}
}
 class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
    if(matrix.length == 0 || matrix[0].length == 0){
        return false;
    }
    int right = matrix[0].length - 1;
    int top = 0;
    while(top < matrix.length && right >= 0){
        if(matrix[top][right] < target){
            top++;
        }else if(matrix[top][right] > target){
            right--;
        }else if(matrix[top][right] == target){
            return true;
        }
    }
    return false;
}
}
上一篇 下一篇

猜你喜欢

热点阅读