# 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)

### 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)

### 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

• 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

official account ： Back end technology .jpg

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