Number of occurrences of numbers in the array (medium difficulty)

Title Overview ( Medium difficulty )

Topic link ：
Point me into the leetcode

Ideas and code

Train of thought display

First of all, this topic uses the original code , Inverse code , Knowledge of complement , If you need help, take a look at this blog and review it ：

Click me to enter the blog
See this for the solution ：
Click to enter the solution
So let's start with the code , Then I will make a supplement to the explanation of the problem

Code example

class Solution {
    
   public int[] singleNumbers(int[] nums) {
    
    int bitmask = 0;
    // XOR all the elements in the array 
    for (int num : nums) {
    
        bitmask ^= num;
    }
    // Because the result of XOR operation is not always 2 Of n The next power ,
    // There may be more than one in binary 1, For the sake of calculation 
    // We just need to keep any of them 1, Everything else is 
    // Let him become 0, What's left here is the one on the far right 1
    bitmask &= -bitmask;
    int[] rets = {
    0, 0};
    for (int num : nums) {
    
        // Then divide the array into two parts , Each part is in 
        // Or, respectively 
        if ((num & bitmask) == 0) {
    
            rets[0] ^= num;
        } else {
    
            rets[1] ^= num;
        }
    }
    return rets;
  }
}

Time complexity ：O(N)
Spatial complexity ：O(1)

analysis ：

for (int num : nums) {
    
        bitmask ^= num;
    }

Here is the XOR of all the numbers , There must be only the last two numbers that only appear once , For example, the group of figures given in the problem solution ：[12,13,14,17,14,12],
When all the numbers in the array are XORed , only 13^17, The result after XOR is 00000000 00000000 00000000 00011100, And one of our code is bitmask &= -bitmask, So at this time bitmask be equal to 00000000 00000000 00000000 00011100, That is to say 28, that (-28) How to calculate? ？ Be careful ： Complement is the binary representation of negative numbers in the computer , here -28 The original code of is 10000000 00000000 00000000 00011100, The reverse code is 11111111 11111111 11111111 11100011, Then the complement is 11111111 11111111 11111111 11100100, that -bitmask = 11111111 11111111 11111111 11100100, and bitmask &= -bitmask As shown in the figure below ：

You can see at this time bitmask The value of is 00000000 00000000 00000000 00000100,
You can see our last 1 Be kept , At this point, our original array can be divided into two groups , One is related to the present bitmask And (&) The result is 0 A set of , Not for 0 A set of ( In fact, this result is not 0 The reason is whether the penultimate number after binary conversion of the number in each array is 1 still 0 of , by 0 Word is 0, by 1 What you say is wrong 0, You can verify it yourself )
So in the end 13 and 17 There must be a different group , then 12 and 14 Each must be in the same group ,12 ^ 12 = 0,14 ^ 14 = 0, So there is only one left in the array 13 and 17, Then return the array .