How to find missing elements

missing elements

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 ！