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

Posted on | In ,

题目

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

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

示例:

现有矩阵 matrix 如下：

1
2
3
4
5
6
7
[
  [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。

题解

这里可以看到对角的性质。

比如二维数组中的(2,2),也就是9的位置。行（0，2）及列（0，2）没有一个大于9的；也就是（x,y）位置上的值，（x,y）矩阵内的值都比（x,y）位置上的值小。但这之外的不一定全都大。虽然上的矩阵是这么弄得。所以target只要一直找到刚好大于的值，再确定范围。

但是还是要考虑一下不同的情况：

  • m == n ：这个情况下就可以顺着对角线一路找下去
  • m > n : 行多于列。那么顺着对角线找下去：1. 小于对角线上最后一个值。那么他就在那个矩阵里。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 暴力法走一波
        int m = matrix.length;

        int n;
        if (m != 0){
            n = matrix[0].length;
        }else{
            return false;
        }
        for (int i = 0 ; i < m; i++){
            for ( int j = 0 ; j < n ; j ++){
                if (matrix[i][j] == target){
                    return true;
                }
            }
        }
        return false;
    }

看答案

  • 标志数引入： 此类矩阵中左下角和右上角元素有特殊性，称为标志数。

    • 左下角元素： 为所在列最大元素，所在行最小元素。
    • 右上角元素： 为所在行最大元素，所在列最小元素。

  • 标志数性质： 将 matrix 中的左下角元素（标志数）记作 flag ，则有:

    1. 若 flag > target ，则 target 一定在 flag 所在行的上方，即 flag 所在行可被消去。

    2. 若 flag < target ，则 target 一定在 flag 所在列的右方，即 flag 所在列可被消去。

本题解以左下角元素为例，同理，右上角元素 也具有行（列）消去的性质。

img

img

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