面试题04. 二维数组中的查找

二维数组中的查找

题目描述

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

示例：

[
[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。

提示：
0 <= n <= 1000
0 <= m <= 1000

转载来源：力扣（LeetCode）

题目分析

这题如果要用暴力法强行寻找的话，时间复杂度将会达到P(N*M)，而且没有有效的利用到题目给的每行每列都是递增的性质，显然不是标准答案，下面介绍一种思维比较灵活的充分利用题目条件的方法：

初始

这是作为例子的矩阵，先取初始化点为18，至于为什么这么取后面再说，先看看算法的步骤：

1. 当前处于18，18 > 9，所以18这一行都比9大，可以舍去这一行，往上走，形成新的矩阵

   
   
   1

2. 当前处于10，10 > 9，所以10这一行都比9大，可以舍去这一行，往上走，形成新的矩阵

   
   
   2

3. 当前处于3，3 < 9，所以3这一行都比9小，可以舍去这一行，往右走，形成新的矩阵

   
   
   3

4. 当前处于6，6 < 9，所以6这一行都比9小，可以舍去这一行，往右走，形成新的矩阵

   
   
   4

5. 当前位于9，返回True

   
   
   5
   
   

   步骤走完了，现在解释一下为什么要选择左下角的点作为起始点（其实相信大家都明白的差不多了），因为它是最后一行最小的元素，同时也是第一行最大的元素，Target比它大的时候就能排除一列，Target比它小的时候就能排除一行，所以无论情况怎么样，都能使下一次寻找的矩阵范围变小，而左上角和右下角的数是做不到的，所以我们可以从左下和右上出发。

时间复杂度：显然O(M+N)
空间复杂度：O(1)

fun findNumberIn2DArray(matrix: Array<IntArray>, target: Int): Boolean {
        var x = matrix.size - 1
        var y = 0
        while (x >= 0 && y < matrix[0].size) {
            if (matrix[x][y] == target)
                return true
            if (matrix[x][y] > target)
                x--
            else
                y++
        }
        return false
    }