LeetCode.137.Single Number II 数组中只出现一次的数2

题目描述

137 Single Number II https://leetcode-cn.com/problems/single-number-ii/

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

相似题目

LeetCode.136.Single Number 数组中只出现一次的数 LeetCode.137.Single Number II 数组中只出现一次的数2 LeetCode.260.Single Number III 数组中只出现一次的数3 LeetCode.剑指offer.056.数组中数字出现的次数

解题过程

位操作，统计所有元素在每位上的和对3求余，由于其他数一定出现3次所以结果就是唯一数在此位的值。此方法还可以推广到所有元素出现了p次只有一个出现了k次的情况。

时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV2020 {
    public int singleNumber(int[] nums) {
        int res = 0;
        // 所有元素在每位上的和对3求余，结果就是唯一数在此位的值
        for (int i = 0; i < 32; i++) {
            int bitSum = 0;
            for(int j = 0; j < nums.length; j++) {
                bitSum += nums[j] & 1;
                nums[j] >>= 1;
            }
            res |= (bitSum % 3) << i;
        }
        return res;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_137_SingleNumber2.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_137_SingleNumber2.java