LeetCode 剑指 Offer 04\. 二维数组中的查找

2022-10-10 08:40

LeetCode 剑指 Offer 04. 二维数组中的查找

@TOC

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例：

1[2  [1,   4,  7, 11, 15],3  [2,   5,  8, 12, 19],4  [3,   6,  9, 16, 22],5  [10, 13, 14, 17, 24],6  [18, 21, 23, 26, 30]7]

提示：

10 <= n <= 1000230 <= m <= 10004

一、解题关键词

1有序 

二、解题报告

1.思路分析

1. 可以暴力
2. 但是必须使用二分解决，二分有两种
3. 行二分，列二分
4. 经典的left right mid 判断是否在该区间内，返回index

2.时间复杂度

3.代码示例

 1class Solution { 2    public boolean findNumberIn2DArray(int[][] matrix, int target) { 3        for(int[] row : matrix){ 4            int index = search(row,target); 5            if(index >= 0){ 6                return true; 7            } 8        } 9        return false;10    }11  //也可以使用Arrays.binarySerach（）d12    int search(int[] nums ,int target){13        int left = 0,right = nums.length - 1;14        while(left <= right){15            int mid = left +(right - left) / 2;16            int num = nums[mid];17            if(num == target){18                return mid;19            }else if(num > target){20                right = mid - 1;21            }else{22                left = mid + 1;23            }24        }25        return -1;26    }27}

代码二：

 1class Solution { 2    public boolean findNumberIn2DArray(int[][] matrix, int target) { 3        int rowLen = matrix.length - 1; 4        int colLen = 0; 5 6        while(rowLen >= 0 && colLen < matrix[0].length){ 7            if(matrix[rowLen][colLen] > target){ 8                rowLen--; 9            }else if(matrix[rowLen][colLen] < target){10                colLen ++;11            }else{12                return true;13            }14        }15        return false;16    }17}

4.知识点

1