编程知识 cdmana.com

How to find missing and repeated elements at the same time

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

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 !

版权声明
本文为[labuladong,]所创,转载请带上原文链接,感谢

Scroll to Top