题解 | #数组中只出现一次的数（其它数出现k次）#

package org.example.test;

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

public class BitTest {

    public static void main(String[] args) {
        int[] nums = {5, 4, 1, 1, 5, 1, 5};
        foundOnceNumber1(nums, 3);
        System.out.println(1 << 5);
    }

    /**
     * 暴力算法
     *
     * @param arr
     * @param k
     * @return
     */
    public int foundOnceNumber(int[] arr, int k) {
        // write code here
        Map<Integer, Integer> map = new HashMap<>();
        for (int value : arr) {
            if (map.get(value) == null) {
                map.put(value, 1);
            } else {
                map.put(value, map.get(value) + 1);
            }
        }
        for (Integer key : map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        return -1;
    }

    /**
     * i
     * 3 2 1
     * 1 0 1
     * 1 0 1
     * 1 0 1
     * 1 0 0
     * 0 0 1
     * 0 0 1
     * 0 0 1
     * <p>
     * i=1: 6%3=0
     * i=2:
     * i=3: 4%3=1
     * 如果 == 1, 表示只出现一次的数这个i为是1，遍历32位，结果相加则为只出现一次的数
     *
     * @param arr
     * @param k
     * @return
     */
    public static int foundOnceNumber1(int[] arr, int k) {
        if (arr == null || arr.length <= 0) {
            return 0;
        }
        int result = 0;
        for (int i = 0; i <= 31; i++) {
            int curBitCnt = 0;
            for (int num : arr) {
                if ((num >> i & 1) != 0) {
                    curBitCnt++;
                }
            }
            if (curBitCnt % k == 1) {
                result += 1 << i;
            }
        }
        return result;
    }
}