一道位运算的算法题

一道位运算的算法题

最近遇到这样一道算法题:

Given an array of integers, every element appears three times except for one. Find that single one.

一组整数,除了一个只出现一次以外,其他每个整数都恰好出现三次,要寻找那个特殊的整数。

似曾相识

首先,它让我想起了另外一道类似的题目,如果把上面的“恰好三次”,改成“恰好两次”,寻找那个特殊的整数,又该怎么解?

那样的话,我希望找到一个方法,让两个相同的数进行运算以后,能够泯灭掉,这样所有的数进行运算,剩下的值就是那个特殊的数。恰好有这样的方法,这个方法就是“异或”:

public int singleNumber(int[] A) {
    int total = 0;
    for (int a : A)
        total ^= a;
    return total;
}

通用算法

“恰好两次”恰好有“异或”来解,现在“恰好两次”变成了“恰好三次”,推广一点说,如果是“恰好N次”,该怎么解?

通用的算法中,用一个HashMap可以得到复杂度近似为n的解法,key为数字本身,value计数,到三次的时候delete掉这个entry,循环完成以后整个HashMap中剩下的就是那个特殊的整数了。这个解法普普通通,没有叙述的必要。这个方法可以保证“恰好N次”一样解决。这个算法很简单,就不写出来了。

另外一个思路,借由位操作,对于整数32位,对于每一位,整个数列的数加起来去取3的余数,就是那个特殊的数在该位上的值。这个方法也可以保证“恰好N次”一样能够被解决:

public int singleNumber(int[] A) {
	int ret = 0;
	for (int i = 0; i < 32; i++) {
		int c = 0, mask = 1 << i;  // ① mask, 第i位为1,其他位都为0
		for (int j = 0; j < A.length; j++) {
		int val = (A[j] & mask);
		if ( val>0 || val<0 ) {  // ② 如果该数在这一位上为1,计数器就加一
			c++;
			}
		}
		if (c%3 > 0)  // ③ 这一位的计数除以3取余数,在这里只可能为0或1
			ret |= mask;
	}
	return ret;
}

关于补码

但是,我在一开始实现这个算法的时候,在上面代码中②的位置,我漏掉了val<0的情况,因为第一印象告诉我,一个正整数去与上一个掩码数,会得到一个正整数。但是这是错误的印象。比如在参数A等于{ -1, -1, -2, -1 }的时候,漏掉val<0的结果等于一个荒唐的2147483646。

这是为什么呢?

因为负数在内存中是以补码方式存放的,第一位最高位是符号位,0表示正数,1表示负数,仅当表示负数的时候,余下的31位等于那个数的数值每一位都取反,然后加1。例如-1,这32位数是:

// 取反加一前:
1(符号位)000 0000 0000 0000 0000 0000 0000 0001
// 取反加一后:
1(符号位)111 1111 1111 1111 1111 1111 1111 1111

32位整数的范围是从-2147483648到2147483647,为何负值比正值能表示的数多一个,就在于这个“加一”(表示0的时候符号位是0,相当于表示0的时候占用了正数的表示法)。

所以,如果漏掉了上面代码中val<0的情况,在执行到i=31的循环的时候,掩码mask即1<<i是-2147483648,因为它把符号位给变成了1,后面都是0:

// 即
1(符号位)000 0000 0000 0000 0000 0000 0000 0000
// 如果按照“取反加一”的规则,它是由它自己取反加一而来的,发生了溢出
1(符号位)000 0000 0000 0000 0000 0000 0000 0000

所以这个数也是补码表示的负数中,最特殊的一个。

那为什么上面说漏掉val<0之后算错的结果是2147483646呢?

这个实际要求解的数-2在内存中的表示是这样的:

// 取反加一前:
1(符号位)000 0000 0000 0000 0000 0000 0000 0010
// 取反加一后:
1(符号位)111 1111 1111 1111 1111 1111 1111 1110
// 符号位错误:
0(符号位)111 1111 1111 1111 1111 1111 1111 1110

由于前面说到的,符号位错误了,变成了正数,而正数的表示法可不是补码表示,所以得出了2147483646这个数。

借助两个数的每一位存储信息

下面这个方法稍微有点难理解,而且很容易写错。需要两个数(one和accumulation),因为一个数在每一位上面无法存放超过两次同样的数出现的信息。每次循环中,需要先标记出现,然后再清零出现过三次的标志位。最终one留下的每一位都是无法清零的,即出现次数不是3的整数倍的。

public int singleNumber4(int A[])
{
	int one = 0; // 出现一次的标志位
	int accumulation = 0; // 积累标志位
	for (int i = 0; i < A.length; i++)
	{
		accumulation |= A[i] & one; // 只要第二次或者以上出现,就为1
		one ^= A[i];  // 出现奇数次保留,偶数次抛弃
		int t = one & accumulation;  // 第三次的时候one和accumulation都保留了该位的值
		one &= ~t;  // 清零出现三次的该位的值
		accumulation &= ~t;
	}
	return one;
}

其实,这道题还有许多其他做法,既包括利用位运算的其他做法,也有那种“先排序,然后再寻找特殊数”这样突破常规想法的解法(其实我觉得先排序这样的做法很好啊,虽然复杂度稍微高一些(取决于排序的时间复杂度了),但是清晰,而且通用性更好。方法虽然简单,但是我大概受到的教条式思维太严重了,这样的方法根本没有想到……)。

==================================================

【2014-11-9】偶然知道还有一种看起来更简单的方式,来自这里

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

欢迎讨论。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接《四火的唠叨》

分享到:

6 comments

  1. 匿名 说道:

    数组求和,让后除以3取余数就是了

  2. Calvinxiao 说道:

    其实我想到了一种解法,就是用快排时的分区算法,对一个数组分好区之后必然一边的长度会是3的倍数,而另一边的不是,那么就继续在长度不是3的倍数那边去找。
    <code>
        public class Solve
        {
            public int find(int[] a)
            {
                int l = 0, r = a.Length – 1;
                while (l < r)
                {
                    Random rand = new Random();
                    int randIdx = rand.Next(l, r + 1);
                    int x = a[randIdx];
     
                    int i = l, j = r;
                    do
                    {
                        while (a[i] <= x) i++;
                        while (a[j] > x) j–;
                        if (i <= j)
                        {
                            int t = a[i];
                            a[i] = a[j];
                            a[j] = t;
                            i++;
                            j–;
                        }
                    } while (i <= j);
                    int left = j – l + 1;
                    if (left % 3 != 0)
                        r = j;
                    else
                        l = i;
                }
                return a[l];
            }
        }
    </code>

  3. ld 说道:

    最后一种解法里面:
    acc |= A[i] & one 
    不能保证出现两次以上的才为1
    假设A[i] 是 1,2, 3, 1, 2, 3, 1即1出现3次,2出现3次,3只出现1次
    循环第一次碰见3的时候(one是1^2 = 3)
    到时acc = 3 |3 = 3,这时3才出现1次,不满足两次以上

  4. 竇小蹦與畫家 说道:

    好吧,我就只想到了你的最後一種辦法… 我也僵化了。。。
    int singleNumber(int array[], int size) {
        // one, two, three
        // the mask code indicating times of 1s for the i-th bits
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < size; ++i) {
            two |= (one & array[i]);
            one ^= array[i];
     
            three = one & two;
            one &= ~three; // clear the third time appeared bits
            two &= ~three;
        }
        return one;
    }
     

  5. 匿名 说道:

    关键是,哪种算得更快?优化算法是为了提高速度
    如果后者花的时间更长,那又有什么意义呢?

发表评论

电子邮件地址不会被公开。

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Preview on Feedage: