文章目录
  1. 1. 排序
  2. 2. HashMap
  3. 3. 位运算
  4. 4. 进一步扩展
    1. 4.0.1. 模拟位运算
    2. 4.0.2. 更节省空间的方法

【题目】:Given an array of integers, every element appears twice except for one. Find that single one.

排序

可以对数组排序,然后遍历一遍,找出不成对的那个数。不过时间复杂度是n^2,太高。

HashMap

用HashMap记录每个数的出现次数。

public int singleNumber(int[] A) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i=0; i<A.length; i++) {
        if (map.get(A[i]) == null) {
            map.put(A[i], 0);
        } else {
            map.remove(A[i]);
        }
    }

    return  map.keySet().iterator().next();
}

时间复杂度是线性,但是有额外的空间消耗。

位运算

两个相等的数的异或运算是0,可以利用这个找到最终的单个数。

public int singleNumber(int[] A) {
    int result =0;
    for (int i=0; i<A.length; i++) {
         result = result ^ A[i];
    }

    return  result;
}

进一步扩展

【题目】:Given an array of integers, every element appears three times except for one. Find that single one.

此题使用上面介绍的前两种方法还是可以解决的。但是异或的方法此处是不适用的,那有木有什么办法可以达到线性的时间复杂度,同时又不使用额外的空间。

模拟位运算

输入是int型数组,所以可以用32位来表达输入数组的元素。

假设输入中没有single number,那么输入中的每个数字都重复出现了数字,也就是说,对这32位中的每一位i而言,所有的输入加起来之后,第i位一定是3的倍数。

现在增加了single number,那么对这32位中的每一位做相同的处理,也就是说,逐位把所有的输入加起来,并且看看第i位的和除以3的余数,这个余数就是single numer在第i位的取值。这样就得到了single number在第i位的取值。这等价于一个模拟的二进制,接着只需要把这个模拟的二进制转化为十进制输出即可。

public int singleNumber(int[] A) {
    int[] count = new int[32];
    int result=0;

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

    return  result;
}

更节省空间的方法

十进制的数字在计算机中是以二进制的形式存储的,所以数组中的任何一个数字都可以转化为类似101001101这样的形式,int类型占内存4个字节,也就是32位。那么,如果一个数字在数组中出现了三次,比如18,二进制是10010,所以第一位和第四位上的1,也都各出现了3次。

因此可以用ones代表只出现一次的数位,twos代表出现了两次的数位。

public int singleNumber3(int[] A) {
    int once = 0;
    int twice = 0;


    for (int i = 0; i < A.length; i++) {
        twice |= once & A[i];
        once ^= A[i];
        int not_three = ~(once & twice);
        once = not_three & once;
        twice = not_three & twice;
    }
    return once;
}

其实不懂这种算法。。。这里暂时记录下来,慢慢研究。

文章目录
  1. 1. 排序
  2. 2. HashMap
  3. 3. 位运算
  4. 4. 进一步扩展
    1. 4.0.1. 模拟位运算
    2. 4.0.2. 更节省空间的方法