Leetcode sword finger offer brush questions - day 22

Leetcode The finger of the sword Offer How to brush questions ：

Leetcode The finger of the sword Offer Brush problem - Learning plan directory _DEGv587 The blog of -CSDN Blog

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

solution ： Group XOR

class Solution {
    public int[] singleNumbers(int[] nums) {
        // Traverse  nums  Execute XOR 
        int n = 0, m = 1, x = 0, y = 0;
        for (int num : nums) {
            n ^= num;
        }
        // here  n = x ^ y
        // Cyclic shift to the left , Calculation  m
        while ((n & m) == 0) {
            m <<= 1;
        }
        // Traverse  nums  grouping 
        for (int num : nums) {
            if ((num & m) != 0) {
                // When  num & m != 0
                x ^= num;
            } else {
                // When  num & m == 0
                y ^= num;
            }
        }
        // Returns the number that appears once 
        return new int[]{x, y};
    }
}

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

Solution 1 ：hashmap

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        for (int n : nums) {
            if (map.get(n) == 1) {
                return n;
            }
        }
        return -1;
    }
}

Solution 2 ： An operation

If a number appears 3 Time , Every bit of its binary also appears 3 Time .

If you add up each bit of the binary representation of all the numbers that appear three times , Then everyone can be 3 to be divisible by .

We add up every bit of the binary representation of all the numbers in the array .

If someone can be 3 to be divisible by , Then this one's of the number that appears only once must be 0.

If someone can't be 3 to be divisible by , Then the position of the number that appears only once must be 1.

class Solution {
    public int singleNumber(int[] nums) {
        int[] k = new int[32];
        for (int n : nums) {
            for (int i = 0; i < 32; ++i) {
                // Cycle every number of hours , Add up each bit of the binary representation of all the numbers in the array separately 
                k[i] += n & 1;
                n >>= 1;
            }
        }

        int ret = 0;
        for (int i = 31; i >= 0; --i) {
            ret <<= 1;
            if (k[i] % 3 == 1) {
                // If someone can't be 3 to be divisible by , that  ret  This bit must be  1
                ret |= 1;// or （ Yes  1  be  1）  Give the location  1
            }
            // If it can be 3 to be divisible by , So this one is right  ret  It must be 0
        }
        return ret;
    }
}