剑指 Offer II 004. 只出现一次的数字

题目

给你一个整数数组nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1:
输入:nums = [2,2,3,2]
输出:3

示例 2: 输入:nums = [0,1,0,1,0,1,100]
输出:100

提示:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次

进阶:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

注意:本题与主站137题重复

题解

public int singleNumber(int[] nums) {
    int result = 0;

    // 从第31位开始 符号位也要判断
    for (int i = 31; i >= 0; i--) {
        int cnt = 0, bit = 1 << i;
        for (int num : nums) {
            // 来判断位元是否为0 若存在符号位 结果为负数
            if ((bit & num) != 0) {
                cnt++;
            }
        }

        // 计算int所有为中1出现的次数 对3取余 剩余的就是只出现了一次的数字
        if (cnt % 3 != 0) {
            // 数字累加
            result |= bit;
        }
    }

    return result;
}