leetcode: 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?

原问题链接：https://oj.leetcode.com/problems/single-number-ii/

 

问题分析

　　其实这个问题本身并不复杂，它只是注明在一个数组里有一个数字出现了一次而其他的数字都出现了３次。为了记录这个数字，我们可以采用这样的一种思路。假定这里的所有数字都是３２位的整数。那么它们每个数字对应的二进制表示就对应着一个３２位里面某些位设置为１。而既然有的数字它们重复了３次。如果我们对这些每位出现１的个数进行统计，所有这些出现３次的数字它们对应的这个位的统计数为３的倍数。而例外的那个元素它在对应的位置出现了仅一次。当然，如果把它们为１的各个位置次数都累加起来，会有一些重叠的情况。比如说这个特殊的数字和其他数字在某个位都是１。

　　通过上述的累加，每个位为１的数字累加无非为以下几个情况。１．该位为所有出现３次数字的累加。这个时候，这个位的累加值必然是３的倍数，即3 * n。　２．　该位为出现３次的数字和这个特殊数字重叠的位置。这样，针对这个位置出现的１的次数为3 * n + 1。　３．该位仅仅是这个特殊数字的位置。这样，这个位置的值为１。　所以，如果要最后只保留这个特殊数字的位该怎么办呢？只要将每个位置的数字对３取模不就得到了么？

　　所以，我们可以很容易得到一个如下的代码：

public int singleNumber(int[] A) {
        if(A == null || A.length == 0) return 0;
        int[] a = new int[32];
        for(int i = 0; i < A.length; i++) {
            for(int j = 0; j < 32; j++) {
                if((A[i] & (1 << j)) > 0)
                    a[j] = (a[j] + 1) % 3;
            }
        }
        int result = 0;
        for(int i = 0; i < 32; i++) {
            if(a[i] > 0)
                result |= (a[i] << i);
        }
        return result;
    }

     在上面的代码里，我们创建一个in[32]的数组。里面每个元素对应整数的一个位。然后我们遍历数组里的每个元素，针对这个元素的每个位和1 << j进行与运算。如果结果大于０，则将该位置的数字加１并对３求模。然后在得到的结果数组里在和０针对每一位进行或运算来恢复这个数字。这里我们依据的是一个数字和当前偏移的i位数字比如1 << i的与运算结果是大于０的。

　　粗粗看来，上面的代码是没问题的。可是如果我们实际中去运行的话，会发现有错误。而且这个错误看起来还不是那么明显。这个问题在哪里呢？我们前面代码里有for(int j = 0; j < 32; j++)  (A[i] & (1 << j )) > 0 这个部分。问题就出在这里。当j比较小的时候，确实1 << j是大于０的。可是当j = 31的时候，1 << 31即２的３１次方。我们知道，这个数字已经超过了int里最大的正数表示了。所以可以说它已经溢出了。如果在代码里尝试去打印输出1 << 31，输出的是一个负数。所以我们前面的代码结果里最高位会是０。为了修正这个问题，我们可以将前面代码里这个判断条件修改为：　

for(int i = 0; i < A.length; i++) {
            for(int j = 0; j < 32; j++) {
                if((A[i] & (1 << j)) != 0)
                    a[j] = (a[j] + 1) % 3;
            }
        }

 或者倒过来，不是将当前的元素每个位和1左移若干位来比对。而是将这个元素向右移位，再和１进行与运算：

for(int i = 0; i < A.length; i++) {
            for(int j = 0; j < 32; j++) {
                if(((A[i] >> j) & 1) > 0)
                    a[j] = (a[j] + 1) % 3;
            }
        }

     这样，前面的代码就正确了。当然，我们的目标不仅仅是能够把代码写出来通过测试。如果能写的更加精炼一点更好。这个时候看前面的代码。在生成这个数字的各个位的时候，后面又要用到这个位的数字。我们完全可以将它们合并起来。这样修改后的代码如下：

public int singleNumber(int[] A) {
        int[] a = new int[32];
        int result = 0;
        for(int i = 0; i < 32; i++) {
            for(int j = 0; j < A.length; j++) {
                if(((A[j] >> i) & 1) != 0)
                    a[i] = (a[i] + 1) % 3;
            }
            result |= a[i] << i;
        }
        return result;
    }

 

总结

　　这个问题看似很简单，但是中间有一些小的细节还是应该非常小心的。不然很容易出错。需要注意的就是溢出和重新构造这个数字的过程。