Leetcode算法Java全解答--74. 搜索二维矩阵

分手后的思念是犯贱 2022-04-03 04:00 155阅读 0赞

# Leetcode算法Java全解答–74. 搜索二维矩阵 #

### 文章目录 ###

*  Leetcode算法Java全解答--74. 搜索二维矩阵
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。  
每行的第一个整数大于前一行的最后一个整数。  
示例:

示例 1:
    
    输入:
    matrix = [
      [1,   3,  5,  7],
      [10, 11, 16, 20],
      [23, 30, 34, 50]
    ]
    target = 3
    输出: true
    示例 2:
    
    输入:
    matrix = [
      [1,   3,  5,  7],
      [10, 11, 16, 20],
      [23, 30, 34, 50]
    ]
    target = 13
    输出: false

## 想法 ##

1.  先编历第一列的数据，找到那个比target大的数据，那么target在这一项的前一行(遍历1/10/23)

在关键行使用二分查找

2.陈独秀方法(better)，把二维数组转换成一个一维数组，直接上二分查找

坐标转换：matrix\[i\]\[j\] <=> matrix\[a\] 其中a=i\*n+j， i=a/n, j=a%n;

## 结果 ##

超过98%的测试案例

时间复杂度/空间复杂度：n/1

## 总结 ##

## 代码 ##

### 我的答案 ###

public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0 || matrix[0][0] > target) {
            return false;
        }
        int muchTargetIndex = -1;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == target) {
                return true;
            } else if (matrix[i][0] > target) {
                muchTargetIndex = i - 1;
                break;
            } else {
                muchTargetIndex++;
            }
        }
    
        int left = 0;
        int right = matrix[muchTargetIndex].length - 1;
        int center = 0;
        while (left <= right) {
            center = left + (right - left) / 2;
            if (matrix[muchTargetIndex][center] == target) {
                return true;
            } else if (matrix[muchTargetIndex][center] > target) {
                right = center - 1;
            } else {
                left = center + 1;
            }
        }
    
        return false;
    }

### 大佬们的答案 ###

public boolean better(int[][] matrix, int target) {
        if(matrix.length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int low = 0, high = m * n;
        while(low < high){
            int mid = (low + high) / 2;
            if(matrix[mid / n][mid % n] == target){
                return true;
            }else if(matrix[mid / n][mid % n] < target){
                low = mid + 1;
            }else{
                high = mid;
            }
        }
        return false;
    }

### 测试用例 ###

@Test
        public void test074() {
            // 创建测试案例
            int[][] arr1 = new int[3][4];
            arr1[0][0] = 1;
            arr1[0][1] = 3;
            arr1[0][2] = 5;
            arr1[0][3] = 7;
            arr1[1][0] = 10;
            arr1[1][1] = 11;
            arr1[1][2] = 16;
            arr1[1][3] = 20;
            arr1[2][0] = 23;
            arr1[2][1] = 30;
            arr1[2][2] = 34;
            arr1[2][3] = 50;
            int target1 = 16;
            int target2 = 13;
    
    
            int[][] arr2 = new int[1][2];
            arr2[0][0] = 1;
            arr2[0][1] = 3;
            int target3 = 3;
    
            // 测试案例期望值
            boolean expResult1 = true;
            boolean expResult2 = false;
            boolean expResult3 = true;
    
            // 执行方法
            Solution074 solution074 = new Solution074();
            boolean result1 = solution074.searchMatrix(arr1, target1);
            boolean result2 = solution074.searchMatrix(arr1, target2);
            boolean result3 = solution074.searchMatrix(arr2, target3);
    
            // 判断期望值与实际值
            Assert.assertEquals(expResult1, result1);
            Assert.assertEquals(expResult2, result2);
            Assert.assertEquals(expResult3, result3);
    
        }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan