leetcode/只出现一次的数字

package com.xcrj;

import java.util.HashMap;
import java.util.Map;

/** * 剑指 Offer II 004. 只出现一次的数字 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 * 考察： * 散列表统计 * 或运算拼接 result |= (1 << i); */
public class Solution4 {
    
    /** * 普通蛮力法 遍历 */
    public int singleNumber(int[] nums) {
    
        int count = 0;
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
    
            result = nums[i];

            for (int j = 0; j < nums.length; j++) {
    
                if (result == nums[j]) {
    
                    count++;
                }
                if (count > 1) {
    
                    break;
                }
            }

            if (count == 1) {
    
                return result;
            }

            count = 0;
        }
        return result;
    }

    /** * 散列表 */
    public int singleNumber2(int[] nums) {
    
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
    
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // findFirst可能有多个只出现1次的数
        return map.entrySet().stream().filter(entry -> entry.getValue() == 1).findFirst().get().getKey();
    }

    /** * 依次计算出现1次元素的每一个二进制位，再使用或运算拼接出出现1次元素 */
    public int singleNumber3(int[] nums) {
    
        int result = 0;
        // 32因为int是32位的
        for (int i = 0; i < 32; ++i) {
    
            int total = 0;
            /** * 求数组中所有元素第i个二进制位的和total * 因为数组中只有出现3次或1次的元素 * 因此total=3*m*1+3*n*0+0/1，m第i位为1的出现3次的元素的个数，n第i位为0的出现3次的元素的个数，出现1次的元素的第i位是0或者1 * 因此出现1次的元素的第i位=total%3 */
            for (int num : nums) {
    
                total += ((num >> i) & 1);
            }
            // 已知 出现1次元素的每一位 通过或运算拼接出出现1次的元素。0左移之后还是0不用或运算拼接
            if (total % 3 == 1) {
    
                result |= (1 << i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
    
        Solution4 solution4 = new Solution4();
        System.out.println(solution4.singleNumber3(new int[]{
    1, 2, 1, 1}));
    }
}