137. 只出现一次的数字 II/面试题56 - II. 数组中数字出现的次数 II(较难)

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

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

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-ii

说明

leetcode137与offer的不是特别一样，但代码都可以跑起来，leetcode要求不使用额外空间，其实也就是状态机，位运算的方式，后面来补（200519）

思路1：

  • 如果一个数字出现三次，则它二进制表示的每一位也出现三次。

    • 如果把所有出现三次的数字的二进制表示的每一位都分别加起来，则每一位的和都能被3整除。
    • 将数组中的所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除，
    • 则只出现一次数字的二进制表示中对应的那一位是0，否则就是1。

作者：luo-jing-yu-yu
链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/wei-yun-suan-_mian-shi-ti-56-ii-shu-zu-zhong-shu-z/

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int singleNumber(int[] nums) {
        //利用二进制，/3==1时即为出现一次
        if(nums==null || nums.length==0)
            return 0;
        int[] bitSum = new int[32];//存储数字二进制的每一位的和
        // int bit = 0;//用以判断该位是0还是1
        for(int num:nums){
            int bitMask = 1;//掩码
            for(int i=31;i>=0;i--){
                int bit = num & bitMask;//与，两者都为1时，则为1             
                // System.out.println(bit);
                if(bit!=0)//这里不能为==1，因为时判断整个num数，而不是每一位
                    bitSum[i]+=1;//若不为0，则将存储每位和的数据该位置+1
                //掩码左移
                bitMask <<=1;//用来判断下一位
            }
        }
        int res=0;
        for(int b :bitSum){
            res<<=1;
            res += b%3;        
        }
        return res;
    }
}