## 编程知识 cdmana.com

### How to find missing and repeated elements at the same time

645. The wrong set

-----------

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 ！

Scroll to Top