Today we are going to do a topic in LeetCode, link to the original topic: reference Offer 04. Lookup in a two-dimensional array

Topic describes

  • In an N by m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Perform an efficient function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.
  • Example:
The existing matrix matrix is as follows: [[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]] for a given target = 5, Returns true. Given target = 20, return false.Copy the code
  • Limitations:
    0 <= n <= 1000
    0 <= m <= 1000
Copy the code

Thought analysis

  • Boundary judgment: matrix is empty or matrix[I] is emptyFalse
  • The first idea: two-layer for loop violence retrieval, performance is not satisfied
  • The second way of thinking: horizontal + vertical double dichotomy, horizontal and vertical are only single direction order, not the whole order, logic is not satisfied
  • The final idea: horizontal dichotomy, vertical traversal, the specific implementation is as follows

code

# Python class Solution(object): def findNumberIn2DArray(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: Def bisect(a, x, lo=0, hi=None): def bisect(a, x, lo=0, hi=None): raise ValueError('lo must be non-negative') if hi is None: hi = len(a) while lo < hi: mid = (lo+hi)//2 if x < a[mid]: hi = mid elif x == a[mid]: return True, mid else: lo = mid+1 return False, lo - 1 if not matrix or not matrix[0]: return False for i in range(len(matrix)): if target < matrix[i][0]: continue elif target == matrix[i][0]: return True else: flag, m_ind = bisect(matrix[i], target) if flag: return True return FalseCopy the code

conclusion

  • Follow-up can try officialA crab movesTheir thinking
    • Starting from the lower left foot node, less is one step up, greater is one step to the right

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign