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

Solutions

1. 二分查找的方式

  最直接的方法就是遍历每一行,每一行作为一个二分查找的子问题来求解:

# -*- coding:utf-8 -*-
class Solution:
    def binary_tree_margins(self, array, l, r, target):
        if l == r:
            return False

        mid_idx = int((l + r) / 2)

        if array[mid_idx] == target:
            return True
        elif array[mid_idx] > target:
            return self.binary_tree_margins(array, l, mid_idx - 1, target)
        else:
            return self.binary_tree_margins(array, mid_idx + 1, r, target)

    def binary_tree_no_margins(self, array, target):
        if len(array) == 0:
            return False
        mid_idx = len(array) / 2 
        if array[mid_idx] == target:
            return True
        elif array[mid_idx] > target:
            return self.binary_tree_no_margins(array[:mid_idx], target)
        else:
            return self.binary_tree_no_margins(array[mid_idx + 1:], target)

    def binary_tree(self, array, l, r, n_cols):
            if l == r:
                return False
            mid_idx = int((l + r) / 2)
            
            row_idx = int(mid_idx / n_cols)
            col_idx = mid_idx % n_cols

            print mid_idx, row_idx, col_idx, array[row_idx][col_idx]

            if array[row_idx][col_idx] == target:
                print '='
                return True
            if array[row_idx][col_idx] > target:
                print '>', l, mid_idx
                return self.binary_tree(array, l, mid_idx - 1, n_cols)
            if array[row_idx][col_idx] < target:
                print '<', mid_idx, r
                return self.binary_tree(array, mid_idx + 1, r, n_cols)
    # array 二维列表
    def Find(self, target, array):
        n_rows = len(array)
        n_cols = len(array[0])
        res_bool = False
        for r in range(n_rows):
            res_bool = res_bool or self.binary_tree_no_margins(array[r][:], target)
        
        return res_bool

if __name__ == '__main__':
    s = Solution()
    array = [[1,2,3,4],[5,6,7,12],[13,17,21,23],[26,28,211,215]]
    target = 7
    print s.Find(target, array)
# 运行时间:312ms
# 占用内存:5752k

  虽然这个办法能够解决,但是效率比较低,$O(n\log n)$ 没有利用到每一列其实也是有序的。

2. 优化解法

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        n_rows = len(array)
        n_cols = len(array[0])
        
        j = n_cols - 1
        i = 0
        while j >= 0 and i < n_rows:
            if array[i][j] == target:
                return True
            elif array[i][j] > target:
                j -= 1
            else:
                i += 1
        return False
# 运行时间:221ms
# 占用内存:5624k

References

  1. 二维数组中的查找