4. 二维数组中的查找

二维数组中的查找

http://www.nowcoder.com/questionTerminal/abc3fe2ce8e146608e868a70efebf62e

  1. 想法:从第0行开始遍历,逐个扫描,如果array[i,j]>target,则抛弃后面的列。
    若小于,则行数加一,这样就可以逐渐缩小搜索范围。
class Solution:
 # array 二维列表
 def Find(self, target, array):
     # write code here
     if not array:return False
     n = len(array)
     m = len(array[0])
     for i in range(n):
         j = 0
         while j < m :
             if array[i][j] == target:
                 return True
             elif array[i][j] < target:
                 j += 1
             else:
                 m = j
     return False

2. 书上的解法:从左下角或者右上角扫描。例如左下角,大于target则i-1,小于则j+1

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if not array:return False
        n = len(array)
        m = len(array[0])
        i = n - 1
        j = 0
        while i >= 0 and j < m:
            if array[i][j] == target:
                return True
            elif array[i][j] < target:
                    j += 1
            else:
                    i -= 1
        return False
  1. 二分法,上面的时间复杂度是O(m+n),从左下角数字开始找直到找到右上角的过程,最坏情况就是m+n.而二分法的时间复杂度是O(log(mn))
    https://leetcode-cn.com/problems/search-a-2d-matrix/
全部评论

相关推荐

评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务