How to find missing and repeated elements at the same time

missing repeated elements 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 ！