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

The title

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.

The sample

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

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

prompt

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 300
  • - 10
    9 ^ 9      <= matrix[i][j] <= 10
    9 ^ 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 ^ 9      <= target <= 10
    9 ^ 9

Their thinking

Violence law

For a matrix lookup target value, the simplest implementation is a two-level walk to find the desired result.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int top = 0, bottom = matrix.length, left = 0, right = matrix[0].length;

        for(int i = top; i < bottom; ++i){
            for(int j = left; j < right; ++j){
                if(matrix[i][j] == target){
                    return true; }}}return false; }}Copy the code

Complexity analysis

  • O(NM)O(NM)O(NM)
  • Space complexity: O(1)O(1)O(1)

dichotomy

There are, however, two additional pieces of information:

  • 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

For orderly arrangement, we can choose dichotomy to shorten the time of investigation.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int top = 0, bottom = matrix.length;

        for(int i = top; i < bottom; ++i){
            int left = 0, right = matrix[0].length;
            while(left < right){
                int mid = left + (right - left) / 2;
                if(matrix[i][mid] == target){
                    return true;
                }else if(matrix[i][mid] < target){
                    left = mid + 1;
                }else{ right = mid; }}}return false; }}Copy the code

Complexity analysis

  • O(NlogN)O(NlogN)O(NlogN)
  • Space complexity: O(1)O(1)O(1)

Binary optimization

For the binary search above, whether the search is conducted by row or column, row by row/column search is required. For the ordered matrix, the value of the current position coordinate point (x, y) must be larger than the value of (x-1, y), (x, y-1), so we can use this feature to narrow the search range. Fan-shaped scan interval elements for compatibility.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;

        while(top <= bottom && left <= right){
            if(matrix[bottom][left] == target){
                return true;
            }else if(matrix[bottom][left] > target){
                --bottom;
            }else{ ++left; }}return false; }}Copy the code

Complexity analysis

  • Time complexity: O(N+M)O(N +M)O(N +M)
  • Space complexity: O(1)O(1)O(1)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/se…