Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [hc-positie [1], [10,11,16,20], [23,30,34,60]], the Output target = 3: trueCopy the code

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Copy the code

Note:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10^4 <= matrix[i][j], target <= 10^4
Copy the code

parsing

An efficient algorithm is developed to search target in m x n integer matrix. The matrix has the following properties:

  • The integers in each row are sorted ascending from left to right
  • The first integer in each line is greater than the last integer in the previous line

In fact, this problem is very easy to solve, just go through all the elements once, so the time is O(N), the space is O(1). However, this solution is too simple and crude. If the size of the matrix is very large, such as about 10^8, then this will run out of time, and a more time-saving algorithm must be sought.

Each row is in ascending order from left to right, and the number in the next row is larger than the number in the previous row. The idea is simple:

  • If matrix[I][0] or matrix[I][-1] equals target, return True.
  • Otherwise, determine whether target is within the range of matrix[I] row data, if so, perform binary search; If the next line is not judged;
  • Return False if there is no result at the end of the loop

If the two algorithms are compared, it is obvious that the binary search method is more time-saving, with time complexity O(logN) and space complexity O(1).

answer

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        for i in range(len(matrix)):
            if target == matrix[i][0] or target == matrix[i][-1]:
                return True
            if matrix[i][0]  < target < matrix[i][-1] :
                return self.search(matrix[i], target)
        return False
    
    def search(self, nums, target):
        i = 0
        j = len(nums) - 1
        while i <= j:
            mid = (i+j) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] > target:
                j = mid - 1
            else:
                i = mid + 1
        return False	
Copy the code

The results

Given the given list in the Python online submission. The linked submissions in the Python online submissions for Search a 2D Matrix.Copy the code

The original link

Leetcode.com/problems/se…

Your support is my biggest motivation