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?

解题方法

记录出现次数

要有extra memory

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

这里可能是signed value,所以对Java有效，python的解不对

利用出现3次的特性

如果对于ith bit的出现次数将它module 3的话，每个bit只能是0或者1，因为除去single number要不就是出现3次，要不0次，module 3 都是0， 再加上single number，只会是0或1

可以用3个 bitmask variables

• ones 来代表ith bit had appeared once
• twos 来代表ith bit had appeared twice
• threes 来代表ith bit had appeared three times

当ith bit出现第三次的时候，将ones和twos里的ith都清0。

Solution

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ones = 0
        twos = 0
        threes = 0
        for num in nums:
            # twos depends on ones and current bit
            # 如果ith bit, ones为1，A[i]也为1，就设为1，否则就保持原值
            twos |= ones & num
            # ones根据现在的i来判断，如果ones本来就是1，又出现，就应该设twos,而将这个ones去掉
            # 当下一次ones从0变为1的时候，才设threes
            ones ^= num
            # threes根据ones和twos,当twos为1，ones又一次从0变成1后，threes设为1
            threes = ones & twos
            # 根据threes将ones和twos对应的Bit清零
            ones &= ~threes
            twos &= ~threes

        #最后返回的是Ones
        #因为出现3次的应该都被清零了，剩下就是single number出现了一次的
        return ones

Reference