【 The finger of the sword offer Answer key 】 Search in a two-dimensional array

Preface

as everyone knows , For an interview ,《 The finger of the sword offer》 It's a book “ Good book ”.

If you're an algorithmic chicken like me , Well, the most recommended is to put your finger first offer To understand the topic of , Next, brush it LeetCode And so on , This is very useful for interview surprise , Because the most common algorithm questions are in this book .

If you find it hard to read this book , You can directly refer to some online code , Copy it again , To understand the algorithm problem is to solve the problem , Copy more questions , You have a feeling about the algorithm problem , This college entrance examination does the fixed routine mathematics question is the same .

For the finger of the sword offer How to solve this series , My idea of writing is , For readers who have read the article , Able to :

  • Quickly understand the frequently asked answers to this question ( Tricks are not included , Save everyone's time , People who really need research can consult other materials )
  • Think as close as possible to the original book ( For example, the interviewers mentioned in the book often ask not to change the original array , Or there's space constraints , Try to embody it in the code , Make sure the reader doesn't miss the details in the book )
  • Try to keep your words simple , Avoid lengthy explanations
  • Give the code to run , The notes are complete , Focus on details
  • The code can be programmed online through Niuke network 《 The finger of the sword offer》 test

《 The finger of the sword offer Answer key 》 series

You can check my 《 The finger of the sword offer Answer key 》 series :

  • Follow my public number : Back end technology , Click on the official account navigation bar. : The finger of the sword offer Answer key
  • The finger of the sword offer Special column of problem explanation (CSDN)
  • Each big blog platform my account ( See the bottom of this article )

Topic introduction

In a two-dimensional array ( Each one-dimensional array has the same length ), Each row is sorted in ascending order from left to right , Each column is sorted in ascending order from top to bottom . Please complete a function , Enter such a two-dimensional array and an integer , Determine whether the array contains the integer .

Their thinking

Method 1

The first thing I can think of is to traverse one row by one or column by column , Determine whether the array contains the integer . This method is obviously the most clumsy two-dimensional array traversal , The interviewer will not be satisfied , The time complexity is O(n^2)

Code

Python

class Solution:
    def Find(self, target, array):
        for i in range(len(array)):
            for j in range(len(array[0])):
                if array[i][j]==target:
                    return True
        return False

Method 2

Let's think about , Since the big numbers are on the right / Underside , Whether we can optimize the next solution by using the data change rules of rows and columns , If the number of targets you're looking for is larger than the number you're looking for , So the target number is on the right or below the current position , If the number of targets you're looking for is less than the number you're looking for , Then the target number is on the left or above the current position . for instance , As shown in the following array :

1  2  3   4
2  3  8   9
3  4  9   10
4  5  10  11

Our position is 1, Want to find 8,8 Greater than 1, So in 1 To the right and bottom of the area for the next step of the search .

If we search his right first ,

2  3   4
3  8   9
4  9   10
5  10  11

We searched under them again ,

2  3  8   9
3  4  9   10
4  5  10  11

At this time we found that

3  8  9
4  9  10
5  10 11

This area was searched twice , We are from the first number in the array [0][0] Taken , There's a problem with duplicate search areas . Is there any way to remove duplicate search areas , We found that , When you take the first number from the top right , You can remove duplicate search areas , Or take this array as an example , take 4, Search for 8, Find out 8 Than 4 Big , that 8 It can't be in 4 This business , Just search from below . If you look for 3,3 Than 4 Small ,4 All the subsequent numbers in that column are greater than 4, Just search from the left .

1  2  3   4
2  3  8   9
3  4  9   10
4  5  10  11

We can also find that the point in the lower left corner can also remove the duplicate search area , In conclusion , It's kind of like variable control , Control a variable , According to the law of another variable , Come to the conclusion .

So we reduce the time complexity to O(n)

Code

Java

public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;
        int cols = array[0].length;
        int i = rows-1, j = 0;
        while(i >= 0 && j < cols){
            if(target < array[i][j])
                i--;
            else if(target > array[i][j])
                j++;
            else
                return true;
        }
        return false;
    }
}

Python

class Solution:
    def Find(self, target, array):
        if array == ([] or [[]]):
            return False
        row = len(array)
        col = len(array[0])
        i=0
        j=col-1
        while 0<=i<row and 0<=j<col:
            if target>array[i][j]:
                i=i+1
            elif target<array[i][j]:
                j=j-1
            else:
                return True
        return False

summary

The title is simple. , What we need to understand is that the algorithm problem should focus on efficiency optimization , Violence can solve the problem , But I can't convince the interviewer .

my 《 The finger of the sword offer Answer key 》 series

You can see it in two ways 《 The finger of the sword offer Answer key 》 series :

  • Follow my public number : Back end technology , Click below the official account. : The finger of the sword offer Answer key
  • The finger of the sword offer Special column of problem explanation (CSDN Navigation page )
  • Blogs of various platforms

Pay attention to me

I'm a back-end development engineer .

Focus on back-end development , Data security , Reptiles , The Internet of things , Edge calculation, etc , Welcome to exchange .

I can be found on all platforms

  • WeChat official account : Back end technology
  • Github:@qqxx6661
  • CSDN:@Rude3Knife
  • You know :@Zhendong
  • Simple books :@ There are three knives
  • Nuggets :@ There are three knives
  • headlines :@ Back end technology

The main content of the original blog

  • Java Review the whole manual for knowledge points
  • Leetcode Algorithm problem analysis
  • The finger of the sword offer Algorithm problem analysis
  • SpringBoot Rookie introduction series
  • SpringCloud Rookie introduction series
  • Reptile related technical articles
  • Back end development related technical articles
  • anecdote / Share good books / Personal interests

Official account number : Back end technology

【 The finger of the sword offer Answer key 】 Search in a two-dimensional array
official account : Back end technology .jpg

If it helps you , May as well collect , Coin-operated , forward , It looks like ~