Leetcode 137 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?

找出只出现一次的数字。

统计每一位出现的次数，对3取余可以得到每一位是否为1

代码语言：javascript复制

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0 ; i < 32; i  )
        {
            int cnt = 0 ;
            for(int j  = 0; j < nums.size() ;j  ) cnt  = ((1 << i) & nums[j])>>i;
            res |= cnt % 3 << i;
        }
        return res;
    }
};

在discuss中看到一种awesome的做法，不是很能理解，知道的朋友可以在评论中告诉我！

代码语言：javascript复制

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;
}

algorithm element memory runtime using

0 人点赞