Collection contains an integer from 1 to n, S, unfortunately, because of data errors, lead to set inside a copied into the inside of the collection of another element values, lead to lost an integer and a collection of elements,
Nums given an array represents the set S after an error occurs as a result, your task is to first find the recurring integer, find missing integer, again will return in the form of an array,
Example 1:
Input: nums=,2,2,4 [1]
Output: [2, 3]
Note:
The length of a given array is [2, 10000],
The given array is unordered,
The code is as follows:
Nums int * findErrorNums (int * and an int numsSize, int * returnSize) {
Int resLianxu=0;
For (int I=1; i
ResLianxu ^=I;//see it from here I know this is to use the solution of an exclusive or operation
}
Int resUnLianxu=0;
For (int j=0; J & lt; NumsSize; J++)
{
ResUnLianxu ^=nums [j];
}
Int resOr=resUnLianxu ^ resLianxu;
Int lastbit=resOr & amp; (- resOr);// since this step I don't understand, why want to use the bitwise and operation here? Why use opposite? Please bosses from here to explain
Int res1=0;
Int res2=0;
For (int m=0; M & lt; NumsSize; M++)
{
If ((nums [m] & amp; Lastbit)==0) res1 ^=nums [m].
The else res2 ^=nums [m].
}
For (int n=1; N & lt; NumsSize + 1; N++)
{
If ((n & amp; Lastbit)==0) res1 ^=n;
The else res2 ^=n;
}
Int * res=(int *) malloc (2 * sizeof (int));
Res [0]=res1;
Res [1]=res2;
For (int z=0; Z & lt; NumsSize; Z++)
{
If (res2==nums [z])
{
Res [1]=res1;
Res [0]=res2;
}
}
* returnSize=2;
return res;
}
CodePudding user response:
To tell the truth, this algorithm belongs to the technique, not very suitable for beginners (without a certain mathematical and logical operations, just don't understand),First of all, you need to know the following logic operations
A ^ b, that is, a or b, when a==b, or the result is 0, that is a number and (same number) to do their own exclusive or operation, the result is 0,
A ^ 0==a, namely arbitrary number and exclusive or 0, the result is the number itself,
A ^ ^ b c==^ ^==b c b c ^ ^ a ^ c====c ^ ^ a ^ b a, which is exclusive or meet the commutative law itself, namely whether operating figures in the front in the different or the same result,
So, to understand what's the result of the resOr first? With LZ sample data to illustrate the
Error collection ns={1, 2, 2, 4}, resUnLianxu is wrong to set all the elements of exclusive or
Right set as={1, 2, 3, 4}, resLianxu is correctly set all the elements of a vision or
ResOr=resUnLianxu ^ resLianxu; Is the error and correct collection of all elements of exclusive or collection of all elements of different or the result to do different or
Equivalent nums set plus arrs set and set of all the elements make exclusive or operation, namely 1 ^ 2 ^ 2 ^ 4 ^ 1 ^ 2 ^ 3 ^ 4
The above said, exclusive or commutative law (to adjust the exclusive or element), and the result is 0, the same number of exclusive or arbitrary number and exclusive or result is 0, the arbitrary number itself,,
ResUnLianxu ^ resLianxu=1 ^ 1 ^ 2 ^ 2 (same number) (same) ^ 2 ^ 3 (different) ^ 4 ^ 4 (same number)=0 ^ 0 ^ 2 ^ 3 ^ 0=2 ^ 3
So resOr is actually wrong different elements of the set and the correct set of exclusive or the results
Next, we put the two set (error set and the correct collection) elements of the group, if we can just put it there are differences between the two elements of the points in the two different group,
According to the above the same way, we put good points set of elements to make exclusive or, you can find out the difference of elements, such as
Error set grouping ns1={1}, ns2={2, 2, 4}//difference number 2 points in the second group
Right set grouping as1={1, 3 }, as2={2, 4}//difference number 3 points in the first set of
So the above we know that if the ns1 and as1 take exclusive or, you can get 3 different elements (1 ^ 1 ^ 3=0 ^ 3= 3 ),
Ns2 and as2 take exclusive or, you can get different elements (2 ^ 2 ^ 4 ^ 2 ^ 4=2 ^ 2 ^ 4 ^ 4 ^ 2=0 ^ 0 ^ 2= 2
So how can the right into this group? Naturally we will first think of parity, an odd number of points a set, a set of the even points,
But if the differences between the two number parity is the same, that is two Numbers as the even or odd number of the person (such as the difference between elements is 3 and 5, or 2 and 6), still can't correct packet, so the parity sex impassability,
So good, we look at, first of all, we know that any of the same number of a, and a number of b do arithmetic, the result must be the same, that is a? A, b, as long as a same? B the result must be the same,
So we don't have to consider two sets of the same element, we only need to care about the difference of the two Numbers, let them and a number of different results after an operation can be grouped correctly,
That is, make differences between number 1 and a 0 after operation, differences in number 2 and a number of operations to the non zero
At this moment we have thought about the resOr (because resOr just is the result of two difference for different or),
So how to distinguish the difference between the two by resOr number? This is resOr & amp; (- resOr),
From the concept of exclusive or shows the result of a ^ b for binary is not the same part of the a and b, pulled out of the binary is not the same part, take the + 1 (two's complement, or negative),
Again and pulled out of the original part with (& amp;) Operations, will keep one same number bits and a or b (because it is the not + 1, take the parts & amp; Result is 0, + 1 part is retained, specific binary derivation can use their hand),
Reserved in this way, if the number of bits and a are the same, it must be a and b is different, because different or take a and b is different parts), and b do so with (& amp;) The result will be 0,
On the other hand, if the number of reserved bits and b are the same, such that it must and a different, and do a and (& amp;) The result will be 0,
At this point, we can be the difference of two Numbers correct grouping, correctly after the grouping, the rest is according to the above analysis of logical processing,
If a for loop ((nums [I] & amp; Lastbit)==0) is the meaning of grouping, error collection into the if the else two groups, right set into the if the else two groups also,
Divided into the two groups just there are differences in the two points on the different group, in this way, through the above analysis of exclusive or operation, can find out the difference of two Numbers,