LeetCode——single-number-ii(出现一次的数2)

知识点：复杂度

本文首发于github

题目描述

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

给定一个数组，除了某一个元素之外的其他元素都出现了三次，找出那个只出现了一次的数。

注意：你的算法应该在线性事件复杂度内完成，不应该使用额外空间。

解题思路

这道题是对single-number的升级，首先回想一下single-number是如何解的，它是用异或运算异或了所有数组中的值最后返回结果，其本质是使用异或计算出所有数中对应bit位只出现了一次的数，如果某一个位有两个数都出现过（两个数一样的情况下），那么那个位就位0，如果某一位只出现过一次，那么那一位就为1。按照这个思路，我们这里只要找出所有数中bit位只出现过1次的就可以，出现过三次的、两次的，都应该是0，那么我们使用三个变量：a ，b，c。

a记录bit位出现过1次1的数值，b记录bit位出现过2次1的数值，c记录bit位出现过3次的位（c=b&a），然后将c中bit值为1的清空为0的就可以了。

代码

public int singleNumber(int[] A) {

        int a = 0;//只出现过1次的位
        int b = 0;//出现过2次的位
        int c;//出现过三次的位
        for (int index = 0; index < A.length; index++) {
            b = b | (a & A[index]);//之前的b或上现在的出现了2次的位
            a = a ^ A[index];//只出现过1次的位
            c = a & b;
            a = a & (~c);//抹去出现了3次的bits,~c将原来是1的都变为0，这样那些为与完之后结果一定是0，原来为0的变为1，这样与的结果由a决定
            b = b & (~c);

        }
        return a;
    }

完整代码