32 ＜ tag array and bit operation ＞ supplement: Lt. sword finger offer 56 - I. number of occurrences of numbers in the array

lt. The finger of the sword Offer 56 - I. The number of occurrences of numbers in an array

[ Case needs ]

[ Thought analysis ]

[ Code implementation ]

class Solution {
    
    public int[] singleNumbers(int[] nums) {
    
        // Because the same number XOR is 0, Any number and 0 The XOR result is itself .
        // Therefore, the final result of traversing the XOR array is the result of two digital XORs that appear only once ： namely  z = x ^ y
        int z = 0;  
        for(int i : nums) z ^= i;
        // According to the nature of XOR, we can know ：z At least one of them is 1, otherwise x And y It's equal .
        // We use an auxiliary variable m To preserve z Which one of them is 1.（ There may be more than one bit for 1, We found the lowest 1 that will do ）.
        // for instance ：z = 10 ^ 2 = 1010 ^ 0010 = 1000, The fourth is 1.
        // We will m Initialize to 1, If （z & m） The result is equal to 0 explain z The minimum is 0
        // Every time we will m Move left one bit and follow z Do and operate , Until the result is not 0.
        // here m It should be equal to 1000, Same as z equally , The fourth is 1.
        int m = 1;
        while((z & m) == 0) m <<= 1;
        // We traverse arrays , Follow each number with m Conduct and operate , The result is 0 As a group , The result is not 0 As a group 
        // For example, for arrays ：[1,2,10,4,1,4,3,3], Let's follow each number with 1000 Do and operate , It can be divided into the following two groups ：
        //nums1 The storage result is 0 Of : [1, 2, 4, 1, 4, 3, 3]
        //nums2 The storage result is not 0 Of : [10] ( Happen nums2 Only one of them 10, If the number in the original array were larger, it wouldn't be like this )
        // At this point, we find that the problem has degenerated into that a number in the array only appears once 
        // Respectively for nums1 and nums2 Traversing XOR will get what we expect x and y
        int x = 0, y = 0;
        for(int i : nums) {
    
            // Here we are through if...else take nums Divided into two groups , While traversing XOR .
            // Create two arrays with us nums1 and nums2 The principle is the same .
            if((i & m) == 0) x ^= i;
            else y ^= i;
        }
        return new int[]{
    x, y};
    }
}

More related topics : 1.＜tag- Hashtable , Arrays and bit operations ＞-lt.136. A number that appears only once + 540. A single element in an ordered array + 137. A number that appears only once II + lt.260. A number that appears only once III 0.1