Single Number II

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

    Note:
    Your algorithm should have a linear runtime complexity. Could you implement it
    without using extra memory?

    Challenge

    One-pass, constant extra space.

    注意到其中的奥义了么？三个相同的数相加，不仅其和能被3整除，其二进制位上的每一位也能被3整除！因此我们只需要一个和int类型相同大小的数组记录每一位累加的结果即可。时间复杂度约为 O((3n+1)\cdot sizeof(int) \cdot 8)

    Python

    1. class Solution(object):
    2.     def singleNumber(self, nums):
    3.         """
    4.         :type nums: List[int]
    5.         :rtype: int
    6.         """
    7.         if nums is None:
    8.             return 0
    10.         result = 0
    11.             bit_i_sum = 0
    12.             for num in nums:
    13.                 bit_i_sum += ((num >> i) & 1)
    14.             result |= ((bit_i_sum % 3) << i)
    15.         return self.twos_comp(result, 32)
    17.     def twos_comp(self, val, bits):
    18.         """
    19.         compute the 2's compliment of int value val
    20.         e.g. -4 ==> 11100 == -(10000) + 01100
    22.         return -(val & (1 << (bits - 1))) | (val & ((1 << (bits - 1)) - 1))

    Java

    1. public class Solution {
    2.     public int singleNumber(int[] nums) {
    3.         int single = 0;
    5.         final int INT_BITS = 32;
    6.         for (int i = 0; i < INT_BITS; i++) {
    7.             int bitSum = 0;
    8.             for (int num : nums) {
    9.                 bitSum += ((num >>> i) & 1);
    10.             }
    11.         }
    13.         return single;
    14.     }
    15. }
    1. 异常处理
    2. 循环处理返回结果result的int类型的每一位，要么自增1，要么保持原值。注意i最大可取 $$8 \cdot sizeof(int) - 1$$, 字节数=>位数的转换
    3. 对第i位处理完的结果模3后更新result的第位，由于result初始化为0，故使用或操作即可完成

    Python 中的整数表示理论上可以是无限的（求出处），所以移位计算得到最终结果时需要转化为2的补码。此方法参考自

    Single Number II - Leetcode Discuss 中抛出了这么一道扩展题：

    We need a array x[i] with size k for saving the bits appears i times. For every input number a, generate the new counter by x[j] = (x[j-1] & a) | (x[j] & ~a). Except x[0] = (x[k] & a) | (x[0] & ~a).

    In the equation, the first part indicates the the carries from previous one. The second part indicates the bits not carried to next one.

    Then the algorithms run in O(kn) and the extra space O(k).

    Java

    1. public class Solution {
    2.     public int singleNumber(int[] A, int k, int l) {
    3.         if (A == null) return 0;
    4.         int t;
    5.         int[] x = new int[k];
    6.         x[0] = ~0;
    7.         for (int i = 0; i < A.length; i++) {
    8.             t = x[k-1];
    9.             for (int j = k-1; j > 0; j--) {
    10.                 x[j] = (x[j-1] & A[i]) | (x[j] & ~A[i]);
    11.             }
    12.             x[0] = (t & A[i]) | (x[0] & ~A[i]);
    13.         }
    14.         return x[l];
    15. }