剑指01-二维数组中的查找

Posted on | In |

题目描述：

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

根据二维数组特性，如果数字target在第m行，则必有array[m][0]<=target 且array[m][N-1]>=target，即大于等于行首元素，小于等于行尾元素。 因此，从第一行m=0到最后一行m=M-1的每行，依次做如下两步检测：

  • 如果array[m][N-1] < target则该行肯定不存在该数，直接进入下一行；
  • 如果array[m][0] > target则整个数组内将不存在该数，返回False。

经过上述检测的某行，则满足array[m][0]<=target 且array[m][N-1]>=target，但这只是必要条件。还需要检查target是否真的在这一行。如果不在这一行，还要继续进入下一行继续检测。

  • 检查target是否真的在这一行，用了二分查找。
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
class Solution:
    def Find(self, target, array):
        def search(num, array):
            if len(array) == 0:
                return False
            s, t = 0, len(array)-1
            while s < t:
                mid = (s+t)>>1
                if array[mid] == num:
                    return True
                elif array[mid] > num:
                    t = mid
                else:
                    s = mid + 1
            return array[s] == num
        
        if array is None or len(array) == 0 or len(array[0]) == 0:
            return False
        M, N = len(array),len(array[0])
        for m in range(M):
            if array[m][N-1] < target:
                # 该行肯定不存在该数，直接进入下一行
                continue
            elif array[m][0] > target:
                # 整个数组内将不存在该数
                return False
            else:
                if search(target, array[m]): 
                    # 如果不在这一行，还要继续进入下一行继续检测
                    return True

将二维数组array看成是平面上\(M\times N\)个小格子组成的一个矩形，则比较某元素array[m][n]与搜索目标target的关系，对搜索空间有如下影响：

  • 如果array[m][n] < target，则任何横坐标\(m'\le m\) 或者纵坐标\(n'\le n\)的小格子都不再考虑,即包括array[m][n]的左上角所有格子组成的小矩形。
  • 如果array[m][n] > target，则任何横坐标\(m'\ge m\) 或者纵坐标\(n'\ge n\)的小格子都不再考虑，即包括array[m][n]的右下角所有格子组成的小矩形。
  • 如果array[m][n] == target，查找结束。

也就是说，如果array[m][n]没有命中，则搜索空间将被抠掉一个以array[m][n]为右下角或者左上角的小矩形。那么，如果每次选择的array[m][n]位于当前矩形空间的左小角或者右上角，那么结果是要么命中，要么搜索空间被抠掉其所在的行或者列，仍然留下了一个矩形的待搜索空间。那么，就可以用迭代来继续按照上述方法做，直到找到或者待搜索空间为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def Find(self, num, array):
        row = 0
        col = len(array[0])-1
        if array == None:
            return False
        while row<len(array) and col >=0:
            if array[row][col] == num:
                return True
            elif array[row][col] > num:
                col -=1
            else:
                row +=1
        return False