首页 > 试题广场 > single-number-ii
[编程题]single-number-ii
现在有一个整数类型的数组,数组中只有一个元素只出现一次,其余元素都出现三次。
注意:
你需要给出一个线性时间复杂度的算法,你能在不使用额外内存空间的情况下解决这个问题么?

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的本质,就是用一个数记录每个bit出现的次数,如果一个bit出现两次就归0,这种运算采用二进制底下的位操作^是很自然的。Single Number II中,如果能定义三进制底下的某种位操作,也可以达到相同的效果,Single Number II中想要记录每个bit出现的次数,一个数搞不定就加两个数,用ones来记录只出现过一次的bits,用twos来记录只出现过两次的bits,ones&twos实际上就记录了出现过三次的bits,这时候我们来模拟进行出现3次就抵消为0的操作,抹去ones和twos中都为1的bits。

public int singleNumber(int[] A) {
       	int ones = 0;//记录只出现过1次的bits
	    int twos = 0;//记录只出现过2次的bits
	    int threes;
	    for(int i = 0; i < A.length; i++){
	        int t = A[i];
	        twos |= ones&t;//要在更新ones前面更新twos
	        ones ^= t;
	        threes = ones&twos;//ones和twos中都为1即出现了3次
	        ones &= ~threes;//抹去出现了3次的bits
	        twos &= ~threes;
	    }
	    return ones; 
    }

发表于 2016-06-07 14:37:47 回复(63)
/*若一个数出现三次,则其对应的二进制数每一位相加必为3或0。
统计数组中所有元素的每一位,若为3的倍数,所求数的该二进制位对3取余为0,否则为1。
**/
public class Solution {
    public int singleNumber(int[] A) {      
       int result=0;
        for(int i=0;i<32;++i){
            int bits=0;
            for(int j=0;j<A.length;++j){
                bits+=(A[j]>>i)&1;//依次获取元素的每一位,并将数组元素相同位相加               
            }
            result|=(bits%3)<<i;
        }
        return result;
    }
}

编辑于 2017-04-20 10:20:53 回复(23)
看不懂这篇可以参考 leetcode :
// discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions/1

写在前面:两个相同的数如果按位异或,最后结果就是0。如果三个数按位相异或(3,3,7),则三个数异或的结果就是7。以下的解法就是建立在这个思路上。异或使得两个相同的数的结果为0,我们要构造使得三个数异或的结果为0的运算。

分析:除了某一个数只出现了1 or 2次(出现次数%3==1 or 2),其余都出现了三次(或整数倍)。也就是说,如果有 模3加法(异或为模2加法),那么就很简单了,直接把所有数字按位相加。但二进制只有0、1,没有2,于是我们可以用两位a、b来表示三进制的两位,a为高位,b为低位。c表示数组A中的某一个数字的一位。则:

上一个a(ta) 上一个b(tb) 现在的c 现在的a 现在的b
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0
注:因为是3进制,并没有a = 1,b = 1的两种情况,在卡诺图中可以随意包含或不包含
总结规律(利用卡诺图)可以得到 :
a = (ta&(~tb)&(~c))|((~ta)&tb&c);
b = ~ta&((~c&tb)|(~tb&c));
得出最后的a、b后,需要得出结果r,a*2+b表示的就是r的某一位(每一位)叠加的次数(%3),比如 a = 1, b = 0,表示r的某一位(每一位)出现了两次(%3) ,即那个单独的数出现了两次,则r的该位应该为1,因为叠加两次,数字就是原来大小的两倍。a = 0,b = 1同理。所以有如下结果:

r a b
0 0
0
1 0 1
1 1 0
注:a = 1 ,b= 1的情况不存在,卡诺图中可以包含也可以不包含。
这里不包含最简单,答案就是  r = a|b
public class Solution {
    public int singleNumber(int[] A) {
        int a = 0 , b = 0;
        for(int c : A){
            int ta,tb;
            ta = a;
            tb = b;
            a = (ta&(~tb)&(~c))|((~ta)&tb&c);
            b = ~ta&((~c&tb)|(~tb&c));
        }
        return a|b;
    }
}

这种方法直接看代码是很难看懂的,必须要清楚思路。
编辑于 2019-03-28 16:42:11 回复(11)
//由于只有一个出现一次的数字,其余都是出现三次,那么有如下思路
// 针对于序列中出现三次的所有数字的每一位来说,相加的结果只有两种
//1+1+1==3 或者0+0+0=0
//那么再加上只出现一次的数字的对应位数字的话,也有两种0或者4
//所以我们可以对上述的每一位求和之后对3取余,结果将会是1或者0
//也就是代表了出现一次的的这个数字对应位置上是1或者0
public class Solution {
    public int singleNumber(int[] A) {
        if(A == null||A.length == 0){
            return -1;
        }
        //得到出现一次的数字的值】
        int result = 0;
        //int为4个字节,那么一共有4*8=32位
        for(int i = 0;i < 32;i++){
            //保存每一位求和值
        	int sum = 0;
            for(int j = 0;j < A.length;j++){
                //累加所有数字上第i位上的数字
                sum+=(A[j]>>i)&1;
            }
            //取余得到第i位上的数字,之后更新result
            result |= (sum % 3) << i;
        }
        return result;
    }
}

发表于 2017-09-05 15:15:29 回复(1)

😁解法一复杂度(n)     解法较复杂 经典!!(内含详细推导,包括真值表,卡诺图)
😀解法二复杂度(32n) 解法较容易  时间复杂度会随数据类型不同增减

解法一解析: 将数据转换为二进制,对数组元素每一位的二进制的10累加起来必然是3N或者3N+1

考虑使用模3加法:    sum = (sum + c) % 3;

对数组元素循环应用模3加法后,最后的结果中,每一位的sum01,该二进制数表示的即为只出现一次的数组元素。

sum可取得值为012,但是二进制数的每一位只能表示01,因此考虑使用两个二进制数(a, b)去表示sum中的高,低位。则000), 101),210

最后结果串中,高位字符串全为0,低位字符串即为正确结果。

真值表:

a ()

b()

c

a(更新后)

b(更新后)

0

0

0

0

0

0

0

1

0

1

0

1

0

0

1

0

1

1

1

0

1

0

0

1

0

1

0

1

0

0

公式: (ab() + c) % 3 = ab()  // a是高位 b是低位

例:二进制: (10 + 1) % 3 = 00

十进制: (2 + 1) % 3 = 0

卡诺图 a():

c\ab()

00

01

10

0

0

0

1

1

0

1

0

卡诺图 b():

c\ab()

00

01

10

0

0

1

0

1

1

0

0

逻辑表达式:

a() = (~c & a() & ~b()) | (c & ~a() & b())

b() = (~c & ~a() & b()) | (c & ~a() & ~b())

将数组A中每个元素应用上述表达式累加后,得到的结果即为:

高位 : 一个全为0的字符串 (逢30,只剩下出现1次的那个数)

低位 : 一个零一串,它表示的正是只出现1次的数的二进制表示

代码:


class Solution {
public:
    int singleNumber(int A[], int n) {
        if (n == 0) return 0;
        int a = 0;
        int b = 0;
        int c;
        int ta, tb;
        for (int i = 0; i < n; i++) {
            c = A[i];
            ta = a;
            tb = b;
            a = (~c & ta & ~tb) | (c & ~ta & tb);
            b = (~c & ~ta & tb) | (c & ~ta & ~tb);
        }
        return b;
    }
};


解法二解析:

将数据转换为二进制,对数组元素每一位的二进制的10累加起来必然是3N或者3N+1Int类型是4字节32位,循环32次,每次循环记录数组元素当前位的二进制累加和,然后将模三后的结果(01)放置在对应位,循环结束即可得到只出现一次的数的二进制表示。

代码:


class Solution {
public:
    int singleNumber(int A[], int n) {
        int sum;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            sum = 0;
            for (int j = 0; j < n; j++) {
                sum += (A[j] >> i) & 1;
            }
            res |= ((sum % 3) << i);
        }
        return res;
    }
};


编辑于 2019-08-09 21:09:48 回复(2)
public class Solution {
    public int singleNumber(int[] A) {
        /**
         * ones:出现1次的bits
         * twos:出现2次的bits
         * threes:出现3次的bits
         * ones = threes & ~twos
         * twos = threes & ~ones
         * 
         * */
        int ones = 0, twos=0;
        for(int i = 0; i < A.length; i++) {
            //xxxs ^ A[i] = threes
            ones = (ones ^ A[i]) & ~twos;
            twos = (twos ^ A[i]) & ~ones;
        }
        return ones;
    }
}
参考了:https://leetcode.com/problems/single-number-ii/discuss/ 

发表于 2017-12-02 15:41:32 回复(1)

思路都差不多,但感觉这样改一下顺序会更加直观:

three完全不依赖前一个three,只依赖于前一个two,所以可以把three先确定下来;

实际上只是维护了one和two,three等同于zero,只是用作辅助,用于把one中的three的部分归零。

public class Solution {
    public int singleNumber(int[] A) {
        int one=0,two=0;
        for(int a:A){
            int three=two&a;
            two=(two&~a)|(one&a); 
            one=one^a&(~three);
        }
        return one|two;
    }
}
编辑于 2019-04-06 14:31:56 回复(0)
class Solution {
public:
    int singleNumber(int A[], int n) {

        int first = 0;
        int second = 0;
        for(int i = 0; i < n ; i++){
            int s = first & A[i] ;  //得出第二次出现位
            int t = second & s ;     //得出第三次出现位
            first |= A[i];           //first保留第一次出现位
            second |= s;             //second保留第二次出现位
            first ^= t;              //first 清空第三次出现位
            second ^= t;             //second清空第三次出现位
        }
        return first ;
    }
};
将每个数字都看成是二进制数,first记录第一次出现的二进制位,second记录第二次出现的二进制位,当二进制位出现三次的时候清空first和second的对应记录位。
发表于 2019-03-30 22:43:46 回复(0)
class Solution {
public:
    int singleNumber(int A[], int n) {
        //int size = sizeof(A);
        set<int> s1;
        set<int> s2;
        if(n<=0)
            return 0;
         
        for(int i=0;i<n;i++)
        {
            if(!s1.insert(A[i]).second)
                s2.insert(A[i]);
        }
        for(int i=0;i<n;i++)
        {
            if(s2.insert(A[i]).second)
                return A[i];
        }
        return 0;
    }
};

发表于 2019-09-19 13:20:41 回复(0)
  • idea:

    1. 当某一位出现三次时约掉
    2. 用two代表出现过两次的位,one代表出现过一次的位,appr代表需要约掉的位
    3. 在two与A[i]同时出现的位要约掉,即appr = two & A[i]
    4. 在one和A[i]同时出现的位要成为two,two除掉约去的位(即two ^ appr也继续是two
    5. A[i]除去约掉的位(即A[i] ^ appr)成为one的候选者,将候选者与one异或即得迭代后的one。
    6. 遍历完以后,one即为只出现过一次(出现三次的都约掉了)的位,此时one即为只出现过一次的数。
  • code

    class Solution {
    public:
      int singleNumber(int A[], int n) {
          if (n == 1) return A[0];
          if (n < 4) return -1;
          unsigned two=0, one=0, appr = 0;
          for (int i = 0; i < n; i++){
              appr = two & A[i]; //在two与A[i]同时出现的位要约掉
              two = (one & A[i]) | (two ^ appr); //在one和A[i]同时出现的位要成为two,two中出现appr(约掉)中没出现的位也要成为two
              one = one ^ A[i] ^ appr; //A[i]中出现appr中没出现的位成为one的候选者,将候选者与one异或即得迭代后的one。
          }
          return one;
      }
    };
编辑于 2019-08-06 15:17:32 回复(0)
class Solution {
public:
    /*
        思路:参考来源:https://leetcode.com/problems/single-number-ii/discuss/43296/an-general-way-to-handle-all-this-sort-of-questions
        这是一个通用的思路,对于类似的一个数组里除了一个数之外其他的数都重复了N次这样的问题,这样的思想可以通吃。
        设置a和b来记录bit操作,a是高位,b是低位,来数为c,对于每一位有:
        a    b    c    comingA    comingB
        0    0    0    0            0
        0    1    0    0            1
        1    0    0    1            0
        0    0    1    0            1
        0    1    1    1            0
        1    0    1    0            0
        注:这里因为是记录三进制的数,因此,不考虑a=1,b=1的情况
        由上图可知以下逻辑表达式:
        comingA=~a&b&c+a&~b+&~c;
        comingB=~a&b&~c+~a&~b&c;
        所以可以得到相应的C语言表达:
        comingA=(~a&b&c)|(a&~b&~c);
        comingB=(~a&b&~c)|(~a&~b&c);
        这样对于结果来说,每一位:
        a    b    res
        0    1    1
        1    0    2
        0    0    3
        由于题目中确定只有res=1和3的情况,因此,结果集每一位的表达简化为:
        a    b    res
        0    1    1
        0    0    0
        即res=a|b;
        以上。
    */
      int singleNumber(int A[], int n) {
        int a=0,b=0;
        for(int i=0;i<n;i++){
            int c=A[i];
            int tempA=(a&~b&~c)|(~a&b&c);
            b=(~a&b&~c)|(~a&~b&c);
            a=tempA;
        }
        return a|b;
    }
};

编辑于 2019-06-17 22:13:04 回复(0)
也是看的别人的代码,很菜理解了很久。这里详细解释下。
之前应该都做过另一个版本的,在一组cp里找单身狗的题,那题很好做,用异或就行,这里换成了3p里找单身狗。想一下上个版本的方法,这题可以用一组操作完成类似与异或的操作。因为前者是两个1之间相互抵消(异或实质上就是1-1化0),有异或这一直接的工具。这里是3个1相消(三元之间显然需要多组操作,因为现有提供操作都是二元,所以还需有变量记录操作结果,即代码中的one,two,three)
这三个变量的解释:
假设给1021011012:表示每位上1出现的个数,逢3化0。显然二进制不允许出现2这样的,而我们的工具(&,|。。。)都是二进制,怎么办,每一位用两个位表示,引出了one,two。
(two,one):(0,0)=0(0,1)=1(1,0)=2(1,1)=3;
第一步:two|=one&t;首先需要更新two;即one中有些1遇到t加一,晋升为2。如果先把one更新了,two用到的是不正确的one;
第二步:one^=t;更新one,没什么好说的,有些1晋升了,又新来一批1;
第三步: three=one&two;(1,1)=3。得到那些为3的位。0010010表示有两位为3
第四,五步:把3位重新置1,新一轮计数。
词不达意,望能理解。
class Solution {
public:
    int singleNumber(int A[], int n) {
        int one=0;
        int two=0;
        int three;
        for(int i=0;i<n;i++)
        {
            int t=A[i];
            two|=one&t;
            one^=t;
            three=one&two;
            one&=~three;
            two&=~three;
        }
        return one;
    }
};
发表于 2019-05-14 10:53:57 回复(1)
public class Solution {

    public static void main(String[] args) {
        int a[] = {2,2,3,2};
        System.out.println(singleNumber(a));
    }
    public static int singleNumber(int[] A) {
        if (A == null || A.length == 0) {
            return new Integer(null);
        }

        int bitSum[] = new int[32];

        for (int i = 0; i < A.length; i++) {
            int bitMask = 1;
            for (int j = 0; j < 32; j++) {
                int bit = A[i] & bitMask;
                if(bit != 0)
                bitSum[j] += 1;
                bitMask = bitMask << 1;
            }
        }

        int result = 0;
        int bitMask = 1;
        for (int i = 0; i < 32; i++) {
            int bit = bitSum[i] % 3;
            result += bitMask * bit;
            bitMask = bitMask << 1;
        }
        return result;
    }
}
发表于 2018-09-07 13:13:54 回复(0)
import java.util.HashMap;
public class Solution {
    public int singleNumber(int[] A) {
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<A.length;i++){
            if(map.containsKey(A[i])){
                map.put(A[i],map.get(A[i])+1);
            }else{
                map.put(A[i],1);
            }
        }
        for(int key:map.keySet()){
            if(map.get(key)!=3){
                return key;
            }
        }
        return 0;
    }
}

发表于 2018-05-30 19:25:57 回复(1)

思路:参考了菜鸟葫芦娃,学工程真是太好了,两位老哥的思路。
single numer本质就是用一个数记录每个bit出现的次数,当数的某一位出现了指定次数就归0(本题是3次)。
假设当出现2次就归0时,很容易想到可以使用异或的方法。
然而,当出现2次以上时,我们就需要增加记录的数,因为一个数每个bit,只有0,1两种可能,只能记录两种。
此处我们就需要使用两个数分别secondbit,firstbit来进行记录,可以表示4种可能,本题只需要3种00,01,10。

然后,使用卡诺图来得到secondbit,firstbit的表达式,分别简化secondbit,firstbit为符号f,s则有:
f卡诺图:

<thead> </thead>
sf\A[i] 0 1
00 0 1
01 1 0
10 0 0

因此有: f = (~s&~f&A[i])|(~s&f&~A[i])

s卡诺图:

<thead> </thead>
sf\A[i] 0 1
00 0 0
01 0 1
10 1 0

因此有: s = (~s&f&A[i])|(s&~f&~A[i])

此外当except one 可能出现1次,也可能出现2次。最后的 s f 可能为 00,01,10 结果就是 a|b,有1出现则此位置为1否则为0

    int singleNumber(int A[], int n) {
        int firstbit = 0,secondbit = 0;
        int one = 0;
        for(int i = 0;i < n; i++){
            one = firstbit;
            firstbit = (~secondbit&~firstbit&A[i])|(~secondbit&firstbit&~A[i]);
            secondbit = (~secondbit&one&A[i])|(secondbit&~one&~A[i]);
        }
        return firstbit|secondbit;
    }

同步博客

发表于 2017-11-27 15:39:19 回复(1)
//one代表只出现了一次的位,two代表出现了两次的位,注意one置一的位two一定不为1,
//反过来一样,然后当出现三次时清零。class Solution {
public:
    int singleNumber(int A[], int n) {
        int one=0,two=0;
        for(int i=0;i<n;i++){
            int tmp=two&A[i];
            two^=tmp;//这两行将之前已经出现两次的位
            A[i]^=tmp;//清零
            
            tmp=one&A[i];
            one^=tmp;//这两行将已经出现了一次的位
            A[i]^=tmp;//清零
            two^=tmp;
            one^=A[i];
        }
        return one;
    }
};
编辑于 2017-08-06 12:02:39 回复(0)
class Solution {
public:
    int singleNumber(int A[], int n) 
    {
        if(A==nullptr || n<=0)
            return 0;
        vector<int>  res(32,0);
        for(int i=0;i<n;i++)
        {
            int bitMask = 1;
            for(int j=31;j>=0;j--)
            {
                int bit = A[i]&bitMask;
                if(bit!=0)
                    res[j] += 1;
                bitMask <<= 1;
            }
        }
        int result = 0;
        for(int i=0;i<32;i++)
        {
            result = result<<1;
            result += res[i]%3;
        }
        return result;
    }
};

发表于 2017-07-04 14:56:34 回复(0)
class Solution {
public:
    int singleNumber(int A[], int n) {
        int bitnum[32]={0};
        int res=0;
        for(int i=0;i<32;i++){
            for(int j=0;j<n;j++){
                bitnum[i]+=(A[j]>>i)&1;
            }
            res|=(bitnum[i]%3)<<i;
        }
        return res;
    }
};
int 整型共有32位,用bitnum[32]存储这n个数据每个二进制位上1出现的个数,再%3,如果为1,那说明这一位是要找元素二进制表示中为 1 的那一位。
发表于 2017-02-25 16:12:22 回复(3)
public int singleNumber(int[] A) {
        //discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions/1
        //这里面有详解,这里主要说一下思想
        //因为出现的是三次,所以需要设计成一个数出现3次之后自动会变为0,这就代表不影响后面的数
      //现在只用bit来表示,a,b可能是0,1的组合,c(next bit)可能是0或者1
        //采用两位a,b来表示.  a ,b 的值可能为0 0 ,0 1 ,10
        //分别代表0次,1次,2次。不可能出现1 1。因为3次之后就清0了
//当对应不同的数字时,无非就是把一位的情况扩展到了32位。但逻辑运算(对于每一位的仍然一样)
        int a = 0;
        int b = 0;
        int ta = 0;
        for(int c : A){
            ta = (~a & b & c) | (a & ~b & ~c);  //这里之所以需要使用ta,是因为计算b的时候需要a的旧值
            b = (~a & ~b & c) | (~a & b & ~c);
            a = ta;
        }
        //we need find the number that is 01,10 => 1, 00 => 0.
        //return a|b 意思是返回出现一次或者出现两次的那个数(假设不知道一个数是出现了一次还是两次)
        //不管只有一个数出现了一次还是两次,另一个数一定为0;相或即可
        return a | b;
}
发表于 2016-08-06 10:35:08 回复(0)
//思路同single-number.先排序,然后顺序遍历,找不一样,返回,如果找不到,返回最后一个,注意数组越界。
//循环时候,i<A.length-1;
import java.util.*;
public class Solution {
    public int singleNumber(int[] A) {
        if(A.length==1){
            return A[0];
        }
        Arrays.sort(A);
        for(int i=0;i<A.length-1;i++){
            if(A[i]!=A[i+1]){
                return A[i];
            }
            i+=2;
        }
        return A[A.length-1];
    }
}
发表于 2017-11-02 15:21:24 回复(0)