编程知识 cdmana.com

How to find missing elements

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

448. Find all the missing numbers in the array

-----------

I've also written a few interesting intelligence questions before , Let's talk about another clever topic today .

The topic is very simple :

Give a length of n Array of , Its index should be in [0,n), But now you have to put it in n + 1 Elements [0,n], So there must be one element that can't hold it , Please find out the missing element .

The problem is not difficult , It should be easy for us to think of , Put this array in order , And then go through it , Isn't it easy to find the missing element ?

Or say , By virtue of the characteristics of data structures , Use one HashSet Save all the numbers in the array , Re traversal [0,n] Number between , Go to HashSet Query in , It's also easy to find out the missing element .

The time complexity of sorting solution is O(NlogN),HashSet The time complexity of the solution is O(N), But it needs to be O(N) Space complexity storage of HashSet.

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 .

The third method is bit operation .

For exclusive or operations (^), We know it has a special property : A number is XOR with itself, and the result is 0, A number and 0 Do XOR or itself .

And XOR operations satisfy the laws of exchange and union , in other words :

2 ^ 3 ^ 2 = 3 ^ (2 ^ 2) = 3 ^ 0 = 3

The missing element can be figured out by these properties . for instance nums = [0,3,1,4]

For ease of understanding , Let's assume that we fill in the index first , Then make each element correspond to its own equivalent index :

After doing so , You can find that in addition to the missing elements , All the indexes and elements form a pair , Now, if you put this single index 2 To find out , And you find the missing element .

How to find this single figure , Just XOR all the elements and indexes , The numbers in pairs will disappear into 0, Only this single element is left , We have achieved our goal .

int missingNumber(int[] nums) {
    int n = nums.length;
    int res = 0;
    //  First XOR with the new index 
    res ^= n;
    //  And other elements 、 Index XOR 
    for (int i = 0; i < n; i++)
        res ^= i ^ nums[i];
    return res;
}

Because the XOR operation satisfies the commutative law and the associative law , So it's always possible to eliminate pairs of numbers , Leaving the missing element .

thus , Time complexity O(N), Spatial complexity O(1), We've reached the best , Should we just go back home ?

If you think so , It shows that we are too poisoned by the algorithm , As we learn more and more knowledge , On the contrary, it is easy to fall into the fixed pattern of thinking , There is actually a very simple solution to this problem : The summation formula of the sequence of equal differences .

The meaning of the title can be understood in this way : Now there's an arithmetic sequence 0, 1, 2,..., n, One of the missing numbers , Please find it out . So this number is not sum(0,1,..n) - sum(nums) Well ?

int missingNumber(int[] nums) {
    int n = nums.length;
    //  The formula :( First item  +  Last item ) *  Number of items  / 2
    int expect = (0 + n) * (n + 1) / 2;

    int sum = 0;
    for (int x : nums) 
        sum += x;
    return expect - sum;

You see , This solution should be the simplest , But tell the truth. , I didn't think of this solution myself , And I went to ask some big guys , They didn't think of the simplest idea either . contrary , If you ask a junior high school student , He may soon be able to think of .

It's done , Should we just go back home ?

If you think so , It shows that our control of the details is almost perfect . In calculating with the summation formula expect when , You think about it The integer overflow Do you ? If the result of multiplication is too large to cause overflow , Then the result must be wrong .

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 .

Our idea just now is to add both sums and subtract them , To avoid spillage , Just sum and subtract at the same time . It's very similar to the idea of bit operation , Still assuming nums = [0,3,1,4], First fill in an index and then match the element with the index :

We let each index subtract its corresponding element , And add up the results of subtraction , It's the missing element ?

public int missingNumber(int[] nums) {
    int n = nums.length;
    int res = 0;
    //  New index 
    res += n - 0;
    //  Add up the difference between the index and the element 
    for (int i = 0; i < n; i++) 
        res += i - nums[i];
    return res;
}

Because addition and subtraction satisfy the law of exchange and law of combination , So it's always possible to eliminate pairs of numbers , Leaving the missing element .

So far, this algorithm has gone through nine twists and eighteen turns , Finally, there is no more pit .

_____________

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