# Written interview topic: looking for the lost pig

2020-11-08 10:30:34

Original published in ： Today's National Day , The Mid Autumn Festival, too , It's really rare . stay 21 Century's 100 During the year , have only 4 Year is like this . At home today , With family , Cook and eat , Do housework , Read some idle books , By the way, write something , I'll go out later , And then come back and run .

The campus autumn recruitment has begun in succession , I wish the students in school get their favorite offer, I also wish the students who are recruited by the society to change jobs smoothly .

today , Let's see A An interview question for the company ：

Yes n Pigs , Take the car to the vegetable market , The pigs were pasted with 1~n The number of , All of a sudden , A pig jumped out of the car and ran away , Ask for the number of the pig that escaped . The pig is still very poor , Slip away , We also need to track down the numbers . below , Let's look at algorithms .

### Algorithm 1： Making difference method

Ideas ：

Step1: To calculate the 1~n And a.

Step2: Find the sum of the numbers of the remaining pigs b.

Step3: a-b That's the number of the pig .

The disadvantage of this algorithm is ： seek 1~n And , It might spill over .

### Algorithm 2： Tagging

Ideas ： Open up an array m, use m[i]=0 or 1 To record i Whether there is , For lost pigs j, There must be m[j]=0.

The disadvantage of this algorithm is ： The space complexity is O(n)

### Algorithm 3： Sequencing

Ideas ： Sort the rest of the pigs , The pig that is running away j At the number of , There must be a break , So they know j The specific value of .

The disadvantage of this algorithm is ： Let's take the example of fast track , Neither time complexity nor space complexity is optimal .

### Algorithm 4： Exclusive or law ( The best algorithm )

Ideas ：

Step1:  To calculate the 1~n Exclusive or values a.

Step2:  Find the exclusive or value of the number of the remaining pigs b.

Step3:  seek a and b Exclusive or values , It's the number of the pig that escaped j.

The principle is as follows :

hypothesis n=5, The number of the lost pig is 3, So the number of the remaining pigs is 2, 4, 1, 5, Let's calculate ：

j = 1^2^3^4^5^2^4^1^5

obviously , According to the exchange law of XOR , The above operations can be simplified , as follows ：

j = 1^1^2^2^4^4^5^5^3 = 3

This gives you the number of the pig that's gone . here , The time complexity is O(n), The space complexity is O(1), This is the best algorithm . As for the procedure , It's simple , So I won't go back to .

In the previous post , We can actually see , XOR is a special kind of “ Addition and subtraction ”, therefore , Algorithm 1 Sum algorithm 4 It's a wonderful thing to do the same . About binary XORs , You can refer to ：