Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

240. Search two-dimensional matrix II

Write an efficient algorithm to search a target value in m x n matrix matrix. The matrix has the following properties:

  • The elements of each row are arranged in ascending order from left to right.
  • The elements of each column are arranged from top to bottom.

  

Example 1: input: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 5 output: trueCopy the code

Example 2: input: matrix = [,4,7,11,15 [1], [2,5,8,12,19], [3,6,9,16,22], [10,13,14,17,24], [18,21,23,26,30]], target = 20 output: falseCopy the code

Tip:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • -10^9 <= matrix[i][j] <= 10^9
  • All elements in each row are arranged in ascending order from left to right
  • All elements in each column are arranged in ascending order from top to bottom
  • -10^9 <= target <= 10^9

Their thinking

We have to find it from rectangular corner, because the elements of each row from left to right in ascending order, from top to bottom of each column ascending order, so we can determine the final line element must be greater than all of the above elements, and the last line is ordered, so if the target is greater than the lower left corner elements, so must appear in the last line, Otherwise, go to the previous line

code

func searchMatrix(matrix [][]int, target int) bool {

	r, c := len(matrix)- 1.0
	for r >= 0 && c < len(matrix[0]) {
		if matrix[r][c]==target {
			return true
		}else if matrix[r][c] < target {
			c++;
		}else{ r--; }}return false
}
Copy the code

  • Time complexity: O(m + N). During the search, if we do not find target, we either decrease y by 1 or increase x by 1. Since the initial values of (x, y) are (0,n−1), y can be reduced at most n times and x can be increased at most m times, and the total search times are m+n. After that, x and y go beyond the boundary of the matrix.

  • Space complexity: O(1).