After reading this article , You can go and get the following questions ：

**-----------**

Let's talk about a simple but ingenious question today , Looking for missing and repeating elements . A previous article 「 Look for missing elements 」 I've also written about similar questions , But the technique used in this and last question is different .

This is a LeetCode 645 topic , Let me describe the subject ：

Give a length of `N`

Array of `nums`

, It was supposed to be `[1..N]`

this `N`

Elements , disorder . But now there are some mistakes ,`nums`

One of the elements in is repeated , It also leads to the loss of another element . Please write an algorithm , find `nums`

Duplicate and missing elements in .

```
// Return two numbers , Namely {dup, missing}
vector<int> findErrorNums(vector<int>& nums);
```

Like input ：`nums = [1,2,2,4]`

, The algorithm returns `[2,3]`

.

It's easy to solve this problem , First traverse the array once , Use a hash table to record the number of times each number appears , And then go through it once `[1..N]`

, Look at the repetition of that element , That element doesn't appear , Just OK 了 .

But the problem is , This normal solution requires a hash table , That is to say O(N) Spatial complexity of . You see the conditions given by the topic are so clever , stay `[1..N]`

There is just one repetition in a few numbers in , One missing ,** When things go out of whack, they will **, Right .

O(N) The time complexity of traversing array is unavoidable , So we can figure out how to reduce the space complexity , Can I O(1) Find repetitive and authentic elements under the spatial complexity of ？

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

### Thought analysis

The characteristic of this problem is , Each element has a certain correspondence with the array index .

We are now transforming ourselves into problems ,** For the time being nums The element in becomes [0..N-1], In this way, each element corresponds exactly to an array index , This makes it easier to understand **.

if `nums`

Duplicate and missing elements are not present in , Then each element corresponds to a unique index value , Right ？

The problem now is , There's a repetition of an element , And it also causes an element to be missing , What will happen to this ？** Will result in two elements corresponding to the same index , And there will be an index with no element corresponding to the past **.

that , If I can do something , Find the index for this duplicate , Is that the duplicate element found ？ Find the index without element , It's just that we found the missing element ？

that , How to determine how many elements of an index correspond without using extra space ？ That's what makes this problem wonderful ：

** By making the element corresponding to each index negative , To indicate that the index has been mapped once **：

If there's a repeating element `4`

, The intuitive result is , Indexes `4`

The corresponding element is already negative ：

For missing elements `3`

, The intuitive result is , Indexes `3`

The corresponding element is a positive number ：

For this phenomenon , We can translate it into code ：

```
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int dup = -1;
for (int i = 0; i < n; i++) {
int index = abs(nums[i]);
// nums[index] Less than 0 Repeat visit
if (nums[index] < 0)
dup = abs(nums[i]);
else
nums[index] *= -1;
}
int missing = -1;
for (int i = 0; i < n; i++)
// nums[i] Greater than 0 It means that you have not visited
if (nums[i] > 0)
missing = i;
return {dup, missing};
}
```

PS：** I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating **. Recommended collection ,** Write the title in the order of my article **, Master all kinds of algorithm set, then put into the sea of questions, like fish .

This problem has been basically solved , Don't forget that we just made it easy to analyze , Suppose the element is `[0..N-1]`

, But the question is `[1..N]`

, So you can get the answer to the original question by simply modifying two places ：

```
vector<int> findErrorNums(vector<int>& nums) {
int n = nums.size();
int dup = -1;
for (int i = 0; i < n; i++) {
// Now the elements are from 1 At the beginning
int index = abs(nums[i]) - 1;
if (nums[index] < 0)
dup = abs(nums[i]);
else
nums[index] *= -1;
}
int missing = -1;
for (int i = 0; i < n; i++)
if (nums[i] > 0)
// Convert index to element
missing = i + 1;
return {dup, missing};
}
```

Actually , Elements from 1 It makes sense at first , It must also start with a non-zero number . Because if the element comes from 0 Start , that 0 The opposite of the number is itself , So if the numbers 0 There is repetition or missing , The algorithm can't judge 0 Have you ever been interviewed . Our previous hypothesis is just to simplify the topic , Easier to understand .

### The final summary

For this kind of array problem ,** The key point is that elements and indexes appear in pairs , The common method is to sort 、 Exclusive or 、 mapping **.

The idea of mapping is what we just analyzed , Map each index and element to , A sign is used to record whether an element is mapped .

The way to sort is also very good to understand , For this question , Imagine if the elements were sorted from small to large , If the corresponding elements of the index do not match , You can find the duplicate and missing elements .

XOR operations are also common , Because of the XOR nature `a ^ a = 0, a ^ 0 = a`

, If you are either an index or an element at the same time , You can eliminate pairs of indexes and elements , What is left is a repeating or missing element . You can look at the previous article 「 Look for missing elements 」, This method has been introduced .

**＿＿＿＿＿＿＿＿＿＿＿＿＿**

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！