题目

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

我的复述：
有一个二维数组

它满足从左往右，从上到下递增的规律，也就是说越接近左上角的数字越小，越接近右下角的数字就越大，现在我们要实现一个高效的算法（函数），查找这个二维数组中是否存在某个值，存在就返回true，不存在返回false。

题解

暴力法

先用一个循环，每次遍历出一个数组nums，然后用sort.SearchInts查出nums数组中target的下标，接着做下判断即可。

//Go实现
func findNumberIn2DArray(matrix [][]int, target int) bool {
	for _, nums := range matrix {
		//遍历数组切片，查找数组中是否含有target值，如果查找不到，返回值是target应该插入数组的位置（会保持数组的递增顺序）
		i := sort.SearchInts(nums, target) //查找nums数组中target的下标
		//插入的位置小于数组长度 且 插入数组的位置上的值和目标值相等
		if i < len(nums) && target == nums[i] {
			return true
		}
	}
	return false
}

leetcode-cn执行：

1
2
3

执行用时：
28 ms, 在所有 Go 提交中击败了80.58%的用户
内存消耗：6.6 MB, 在所有 Go 提交中击败了70.78%的用户

牛客网运行：

运行时间：7ms
超过8.42%用Go提交的代码
占用内存：3204KB
超过44.21%用Go提交的代码

双指针

举例，查找数字8：

先让指针i和j都集中在左下角18的位置上，当发现18>8，那就说明18这一整行都大于8，因此将指针i向上移动一个位置；
当发现10>8，那就说明10这一整行都大于8，因此将指针i向上移动一个位置；
当发现3<8，那就说明从数字3往上这一列，都比目标值8要小，因此将指针j向右移动一个位置；
当发现6<8，说明从数字6往上这一列，都比目标值8要小，因此将指针j向右移动一个位置；
当发现9>8，说明数字9向右边一整行的数字都大于8，因此将指针i向上移动一个位置；
当发现8=8，说明目标值8是存在的。

//java实现
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //从数组的左下角位置开始去搜索整个二维数组
        //1，当发现当前遍历的元素大于target时，意味着这个元素后面的所有元素也都大于target，那么就不用去搜索这一行了
        //2，当发现当前遍历的元素小于target时，意味着这个元素上面的所有元素也都小于target，那么就不用去搜索这一列了
        
        //初始化i和j为数组左下角元素
        //最后一行
        int i = matrix.length - 1;
        
        //第0列
        int j = 0;
        
        //从数组的左下角开始出发，只要 i 和 j 没有越界继续判断
        while(i >= 0 && j < matrix[0].length) {
            //当发现当前遍历的元素大于target时，意味着这个元素后面的所有元素也都大于target
            if (matrix[i][j] > target) {
                //行索引向上移动，即i--，即消去矩阵第i行元素
                i--;
            //当发现当前遍历的元素小于target时，意味着这个元素的所有元素也都小于target
            } else if (matrix[i][j] < target) {
                //列索引向右移动一格，即j++，即消去矩阵第j列元素
                j++;
            //否则，说明找到目标值
            } else {
                return true;
            }
        }
        
        return false;
    }
}

leetcode-cn执行用时

1 2	执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户内存消耗：47.3 MB, 在所有 Java 提交中击败了31.35%的用户

不会飞的章鱼

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

题目

题解

暴力法

双指针