# The finger of the sword Offer 56 - II. The number of occurrences of numbers in an array II：

In an array `nums` Except that a number appears only once , The other numbers appear three times . Please find the number that only appears once .

# Examples 1：

`````` Input ：
nums = [3,4,3,3]

Output ：
4
``````

# Examples 2：

`````` Input ：
nums = [9,1,7,9,7,9,7]

Output ：
1
``````

# Tips ：

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 231

# analysis

• Facing this algorithm problem , The second leader was lost in thought .
• This problem should be solved with ideas , You can use at least one hash Watch to count , But waste the extra space .
• You can also use bit operations , XOR can count bits that occur an odd number of times , Except that the target number appears once , The other numbers appear three times , How to distinguish between one and three times in one traversal ？ You can use two additional variables ones（ The record shows 3 A multiple of 1 Secondary bit , Or the number of occurrences is right 3 Modulus of 1） and twos（ The record shows 3 A multiple of 2 Secondary bit , Or the number of occurrences is right 3 Modulus of 2） To record the status of bits , You can only leave the number that appears once .

## rust

``````impl Solution {

pub fn single_number(nums: Vec<i32>) -> i32 {

let mut ones = 0;
let mut twos = 0;

nums.iter().for_each(|num| {

ones = (ones ^ num) & !twos;
twos = (twos ^ num) & !ones;
});

return ones;
}
}
``````

## go

``````func singleNumber(nums []int) int {

ones := 0
twos := 0

for _, num := range nums {

ones = (ones ^ num) & ^twos
twos = (twos ^ num) & ^ones
}

return ones
}
``````

## typescript

``````function singleNumber(nums: number[]): number {

let ones = 0;
let twos = 0;

for (const num of nums) {

ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}

return ones;
};
``````

## python

``````class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones, twos = 0, 0
for num in nums:
ones = (ones ^ num) & ~twos
twos = (twos ^ num) & ~ones
return ones

``````

## c

``````int singleNumber(int* nums, int numsSize){

int ones = 0;
int twos = 0;

for (int i = 0; i < numsSize; ++i) {

ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ~ones;
}

return ones;
}
``````

## c++

``````class Solution {

public:
int singleNumber(vector<int>& nums) {

int ones = 0;
int twos = 0;

for (int num: nums) {

ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}

return ones;
}
};
``````

## java

``````class Solution {

public int singleNumber(int[] nums) {

int ones = 0;
int twos = 0;

for (int num : nums) {

ones = (ones ^ num) ^ twos;
twos = (twos ^ num) & ~ones;
}

return ones;
}
}
``````