给定一个数组,除了一个数出现1次之外,其余数都出现3次。找出出现一次的数。

如:{1, 2, 1, 2, 1, 2, 7}, 找出7.

格式:

第一行输入一个数n,代表数组的长度,接下来一行输入数组A[n],(输入的数组必须满足问题描述的要求),最后输出只出现一次的数。

要求:

你的算法只能是线性时间的复杂度,并且不能使用额外的空间哦~

样例输入

4
0 0 0 5
样例输出

5

3 5 收藏


直接登录
最新评论
  • 韩子迟 web 工程师 2016/06/10

    我们以数组`[1, 2, 3, 1, 2, 1, 2]`举例,将数组元素用二进制表示:

    0 1
    1 0
    1 1
    0 1
    1 0
    0 1
    1 0

    如果理解了上题,此题的思路似乎也就呼之欲出了。我们也可以按位运算,计算1 bit的数量,如果每个数字都出现三次,那么每位上的1 bit数量肯定是3的倍数,相反如果不是3的倍数,那么就是那个特殊的数在捣蛋。

    我们似乎需要这么一种“加法”运算,使得每位上的 1 bit 数量能够得到累计,并且累计到了3就自动清零。但是理想是美好的,现实是残酷的,并没有这样一种神奇的运算(三进制?)。

    但是我们可以用一个数“辅助”,因为每一位的1 bit数量统计都是类似的,所以假设正在统计某一位的1 bit数量。我们用`a`来表示 1 bit 的数量,当 1 bit 的数量为0时,a=0;当数量为1时,a=1;当数量为2时,a=2?非也,位运算只能表示0和1,所以这时我们引进第二个变量b,我们用b=1来代表已经有了2个 1 bit,所以当有两个 1 bit 时,a=0,b=1。数量统计结果逢3化0,所以只有0、1、2三种结果:

    bits数量 a b
    0 0 0
    1 1 0
    2 0 1

    思路也就显而易见了,每次运算我们维护a和b的值,运算到最后即可得到结果:

    var singleNumber = function(nums) {
    var a = 0, b = 0;
    nums.forEach(function(item) {
    b = a & (b ^ item);
    a = b | (a ^ item);
    });

    return a;
    };

    • 王先生 学生 2016/06/11

      思路理解了,但JS没有学过,可否写个java版

      • 韩子迟 web 工程师 2016/06/11

        不需要了吧,就几行代码,猜也能猜出意思了吧。。

         

      • 风萧萧梦潇 学生 2016/06/11

         

      • 王念一 高一学生 2016/10/06

        怎么踩的…………

    • sdkl   2016/06/11

      a = b | (a ^ item);这句好像有点问题。是否要改为a = (!b) & (a ^ item)?

    • 风萧萧梦潇 学生 2016/06/11

      数量为2的时候好像a和b都是1?

    • 加州清光 学生 2016/06/11

      核心两句看不懂啊,求点拨。

      什么叫逢3化0?如果是题例答案7呢?

      算法手算步骤:

      001: b=0, a=1

      011: b=1, a=3(001, 011)

      001: b=0, a=2(000, 010)

      011: b=2, a=3(010, 011)

      001: b=1,  a=5(001, 101)

      011: b=0, a=6(000, 110)

      111: b=6, a=7(110, 111), 7 is the answer

      • 加州清光 学生 2016/06/12

        好吧我能理解这个结果,逢一次b不变,a变为该数;逢二次b为该数,a为该数;逢三次归零。

        但是这两句的逻辑含义是什么?没理解。

        b = a & (b ^ item);
        a = b | (a ^ item);

  • M_Kepler 学生 2016/06/12

    没有想到网易用的是老题目啊,之前写过:https://github.com/M-Kepler/algorithm/blob/master/all_three_but_one.cpp

  • Sandmangel 财务出纳。 2016/08/31

    一个最简单的方法,直接计重复,设如果数A与数B为重复值,可以直接找等同于A或B值不作比较,匹配下一个数。若无重复,比较完,直接写上去

  • 左胤和   2016/10/06

    整那么麻烦干什么,来个简单的方法

    假设所有重复的数为,a1,a2,…..,an

    不重复的数为,b,那么整个数组的和,sum=3a1+3a2+…..+3an+b

    假设有S=a1+a2+….+an+b,我们只需要遍历一次数组计算出sum和S的值,就很容易得到b的值了,

  • 王念一 高一学生 2016/10/06

    神提莫2017

    还没到呢好不

  • 龙雀 野生程序员 2016/10/09

    开32个byte/short,分别记录每位的情况。时间上是O(32n) = O(n),空间上是O(32) = O(1)。

  • 数组冒泡排序,然后定义3个数组a.b.c,将排序后的数组依次写入a.b.c中,输出数组a的和减数组b的和,就是那个只出现一次的