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] < 2³¹

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 .

Answer key

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

Original title transmission gate ：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/

Thank you very much for reading this article ~
welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~
It's not hard to give up , But persistence must be cool ~
I hope all of us can make a little progress every day ~
This paper is written by The white hat of the second leader ：https://le-yi.blog.csdn.net/ Original blog ~