Given an array of integers, nums, each element appears exactly three times except for one element. Find and return the element that appears only once.

 

Example 1:

Nums = [2,2,3,2] Output: 3 Example 2:

Input: nums = [0,1,0,1,0, 99] Output: 99

Tip:

1 <= nums.length <= 3 * 104-231 <= nums[I] <= 231-1

Their thinking

Because every element appears exactly three times except for one, align the binaries of all elements in a column where the number of 1 occurrences in each column (that is, the same bit) can only be a multiple of 3 or a multiple of 3 plus one.

Why is it a multiple of three or a multiple of three plus one?

Because the array consists of two parts, n triples (the same three elements) and a single element, and because the same element has the same value in the same binary bit, it may produce 3m (n>=m) ones (if the single element is 0), or the single element may have the same 1 bit. So 3m+1 (n>=m) ones are possible.

So with the number of ones, you can derive all the bits that are 1 for the independent element, and you can restore the independent element

code

func singleNumber(nums []int) int {

	res:=int32(0)
	for i := 0; i < 32; i++ {// Check each binary bit
		c:=int32(0)
		for _, num := range nums {
			c+=int32(num)>>i&1
		}
		if c%3>0{// Restore individual elements
			res|=1<<i
		}
	}
	return int(res)
}
Copy the code