[1] 二维数组中的查找(中等)
[1] 二维数组中的查找(中等)

题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[[1,2,8,9],  [2,4,9,12],  [4,7,10,13],  [6,8,11,15]]
给定 target = 7,返回 true
给定 target = 3,返回 false
输入:7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值:true
说明:存在7,返回true
输入:3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值:false
说明:不存在3,返回false

解题思路

暴力法

/**
 * 暴力法
 * T(n^2) S(1)
 */
public boolean Find(int target, int[][] array) {
    for (int i = 0; i < array.length; i++) {
        if (array[0].length > 0 && target >= array[i][0] && target <= array[i][array[i].length - 1]) {
            int a = 0;
            int b = array[i].length - 1;
            while (a < b) {
                if (array[i][a++] == target || array[i][b--] == target) {
                    return true;
                }
            }
        }
    }
    return false;
}

二分法

选择从左下角或右上角开始进行判断,如果坐标数比目标数小,则往下移动一行,如果坐标数比目标数大,则往前移动一列。
notion image
/**
 * 二分法
 * T(m+n) S(1)
 */
public boolean Find(int target, int[][] array) {
    if (array.length == 0 || array[0].length == 0) {
        return false;
    }
    int x = array[0].length - 1;
    int y = 0;
    // x、y 初始化为右上角
    while (x >= 0 && y < array.length) {
        if (target == array[y][x]) {
            return true;
        } else if (target > array[y][x]) {
            // 目标数大则去下一行找
            y++;
        } else {
            // 目标数小则去前一列找
            x--;
        }
    }
    return false;
}