@[toc]

Synchronize GitHub here at 👉Github.com/TeFuirnever…

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array

1, dry

Lookup in a two-dimensional array 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. Limit: 0 <= n <= 1000 0 <= m <= 1000 https://leetcode-cn.com/problems/search-a-2d-matrix-ii/ 211,829 votes 525,418 submissionsCopy the code

Binary search tree

Each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom.

Algorithm flow:

  1. If matrix is empty, return false;
  2. Start from the element in the lower left corner of matrix (index set to (I, j)) and compare with the target value:
    1. When matrix[I][j] == target, return true, representing target value found.
    2. When matrix[I][j] > target, execute I –, that is, eliminate the ith element;
    3. When matrix[I][j] < target, j++ is executed, that is, the JTH column element is eliminated;
  3. If the row or column index is out of bounds, there is no target value in the matrix and returns false.
    1. After each I or J move, a “new matrix with one row (column) eliminated” is generated, and the index (I, j) defaults to the lower-left element (flag number) of the new matrix.
// Interview question 04. Search in a two-dimensional array
// Standard practice
class Solution {
public:
	bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
		if (matrix.empty() || matrix[0].empty()) return false;
		int i = matrix.size(a)- 1, j = 0;
		while (i >= 0 &&  j < matrix[0].size())
		{
			if (matrix[i][j] == target) return true;
			if (matrix[i][j]>target) i--;
			else j++;
		}
		return false; }};Copy the code

4. Complexity

/* Time complexity: O(n+m). Rows of subscripts accessed are incremented at most n times and columns are decreased at most m times, so the body of the loop is executed at most N + m times. Space complexity: O(1) */
Copy the code

— — — — — — — — — — — — — — — — — — —

  • Finger Offer (C++ version) series: master table of contents and some instructions for improving efficiency
  • Finger Offer (C++ version) series: repeated numbers in the finger Offer 03 array

— — — — — — — — — — — — — — — — — — –

This article is supported by LeetCode, Niuke, the public ha Oh, Zhihu!

Leetcode-cn.com/u/tefuirnev…

blog.nowcoder.net/wsguanxl

Mp.weixin.qq.com/s/bDwxwQfZy…

www.zhihu.com/people/tefu…