Leetcode 137. Single Number II

算法 Java Leetcode

Find the single integer II.

Question

Given an array of integers, every element appears three times except for one. Find that single one.
See it on Leetcode

Example: Given int[] arr = {1, 2, 1, 1, 3, 4, 3, 3, 2, 2}, return 4.

Hint

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

Solution

• java
• cpp

public class Solution {
    public int singleNumber(int[] nums) {
        int one = 0, two = 0;
        for (int i = 0; i < nums.length; i++) {
            two |= nums[i] & one;
            one ^= nums[i];
            int three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;  
        for (int i = 0; i < nums.size() ; i++)  
        {  
            two |= nums[i] & one;  
            one ^= nums[i];  
            int three = one & two;  
            one &= ~three;  
            two &= ~three;  
        }  
        return one;
    }
};