240、矩阵搜索II

leetcode 数组二分查找分治矩阵

Created At : 2020-07-26 00:19

Count:483 Views 👀 :

Comment:

240、矩阵搜索II
1. 示例:
分析

240、矩阵搜索II

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

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

示例:

现有矩阵 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false

链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii

分析

在一个行列从小到大都是递增的矩阵中快速查找目标值。

二维枚举

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int element : row) {
                if (element == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

二分搜索

每一行进行二分查找。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = search(row, target);
            if (index >= 0) {
                return true;
            }
        }
        return false;
    }

    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

Z型二维搜索

边界递减发
获取矩阵的行长 r和列长 c
遍历矩阵行[0,r]) 列 [c-1,0]
- 找到，标记=ture
- 偏大
  - 行缩–
- 偏小
  - 列缩++
返回是否可以找到

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        boolean flag = false;
        int r = matrix.length,c;// 获取行数
        if (r > 0){
            c = matrix[0].length;// 获取行的元素个数
        }else{
            return false;
        }
        // 横纵查找，
        // i 为纵向，负责从小到大遍历
        // j 为横向，负责从大到小遍历
        for (int i = 0,j = c - 1;i < r && j >= 0;){
            if (matrix[i][j] == target){
                flag = true;
                break;
            }
            if (matrix[i][j] > target){ // 当前值大了
                j--; // 行缩
            }else { // 当前值小了
                i++; // 列缩 
            }
        }
        return flag;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com