每日一题-20240307

发表于 更新于 分类于 阅读次数： 本文字数： 582 阅读时长 ≈ 2 分钟

题目描述

240. 搜索二维矩阵 II

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

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

示例 1：

img

1
2
输入：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

示例 2：

img

1
2
输入：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 = 20
输出：false

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -109 <= matrix[i][j] <= 109
  • 每行的所有元素从左到右升序排列
  • 每列的所有元素从上到下升序排列
  • -109 <= target <= 109

解题思路

遍历

我们直接遍历整个矩阵 matrix，判断 target是否出现即可。

二分查找

由于矩阵 matrix 中每一行的元素都是升序排列的，因此我们可以对每一行都使用一次二分查找，判断 target 是否在该行中，从而判断 target 是否出现。

Z字形查找

代码实现

遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution240Case1 {
    /**
     * 遍历
     *
     * @param matrix
     * @param target
     * @return boolean
     * @author Forest Dong
     * @date 2024/04/01 19:18
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (target == matrix[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] 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}};
        System.err.println(searchMatrix(matrix, 5));
    }
}

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution240Case2 {
    /**
     * 二分查找
     *
     * @param matrix
     * @param target
     * @return boolean
     * @author Forest Dong
     * @date 2024/04/01 19:18
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            if (search(row, target) >= 0) {
                return true;
            }
        }
        return false;
    }

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

    public static void main(String[] args) {
        int[][] 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}};
        System.err.println(searchMatrix(matrix, 5));
    }
}

Z字形查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution240Case3 {
    /**
     * 二分查找
     *
     * @param matrix
     * @param target
     * @return boolean
     * @author Forest Dong
     * @date 2024/04/01 19:18
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n - 1;
        while (x <= m && y >=0) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                y--;
            } else {
                x ++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] 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}};
        System.err.println(searchMatrix(matrix, 5));
    }
}