最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇11_搜索二维矩阵 II [难度:中等]

XAMPP相关 admin 559浏览 0评论

来源:LeetCode

难度:中等

描述:

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

示例1:

drf38

示例2:

drf038

分析:题意就是给一个二维数组和一个目标值,让咱们看这个值是否在二维数组中,首先想到的就是暴力法,遍历搜索整个数组一一比较即可,紧接着咱又看到数组中每行和每列都是升序排序,对于排序的数据咱们自然又能想到二分法来解,咱们在仔细瞅瞅,会发现每行和每列都是升序排序的结果就是每个数会比它的右边小,上边大(边界值例外),有点像二叉搜索树…,以下是具体解法

解题

方法一:暴力法

思路:遍历数组中的每个元素,一一对比

代码:

 1public boolean searchMatrix(int[][] matrix, int target) {
 2    for (int i = 0; i < matrix.length; i++) {
 3        for (int j = 0; j < matrix[0].length; j++) {
 4            //没啥好说的,一一遍历、一一对比,相等返回true即可
 5            if (matrix[i][j] == target) {
 6                return true;
 7            }
 8        }
 9    }
10    return false;
11}

时间复杂度:O(mn)

空间复杂度:O(1)

 

方法二:二分法

思路利用每行递增特性,遍历数组的每行,在每行中进行二分查找

 1public boolean searchMatrix(int[][] matrix, int target) {
 2    if (matrix == null || matrix.length == 0) {
 3        return false;
 4    }
 5    for (int i = 0; i < matrix.length; i++) {
 6        //对每行进行二分查找
 7        if (binarySearch(matrix, i, target)) {
 8            return true;
 9        }
10    }
11    return false;
12}
13
14//二分查找
15private boolean binarySearch(int[][] matrix, int row, int target) {
16    int end = matrix[row].length - 1;
17    int start = 0;
18    while (start <= end) {
19        int mid = (end - start) / 2 + start;
20        //固定横坐标,利用每行升序排序特性
21        if (matrix[row][mid] == target) {
22            return true;
23        } else if (matrix[row][mid] > target) {
24            end = mid - 1;
25        } else {
26            start = mid + 1;
27        }
28    }
29    return false;
30}

时间复杂度:O(m logn)

空间复杂度:O(1)

 

方法三:二叉搜索法

思路:利用数组每列从上到下升序排序,每行从左到右升序排序,那么每个元素比与其相邻的右节点要小,比上节点要大,那么咱可以将整个二维数组看成一个二叉搜索树,最左下角的那个节点为根节点(你品..你细品…),如下直观图

drf0038

代码:

 1public boolean searchMatrix(int[][] matrix, int target) {
 2    if (matrix == null || matrix.length == 0) {
 3        return false;
 4    }
 5    int startI = matrix.length - 1;
 6    int startJ = 0;
 7    //根节点 左下角 matrix[startI][startJ]
 8    while (matrix[startI][startJ] != target) {
 9        //比根大,往右走,startJ 加1
10        if (matrix[startI][startJ] < target) {
11            startJ++;
12        } else if (matrix[startI][startJ] == target) {
13            return true;
14        } else {
15            //比根小,往上走,startI 减一1
16            startI --;
17        }
18        //边界判断
19        if (startI < 0 || startI > matrix.length - 1 
20                || startJ < 0 || startJ > matrix[0].length - 1) {
21            return false;
22        }
23    }
24    return true;
25}

时间复杂度:O(m + n)

空间复杂度:O(1)

 

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇11_搜索二维矩阵 II [难度:中等]

您必须 登录 才能发表评论!