首页 > itarticle > leetcode 137. single number ii

leetcode 137. single number ii

admin 11月 12, 2020 0

算法
Java
Leetcode

Question

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

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