编程知识 cdmana.com

[algorithm leetcode] sword finger offer 56 - ii Number of occurrences of numbers in the array II (Multilingual Implementation)



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 .

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 ~


版权声明
本文为[White hat of the second leader]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/174/202206231834278280.html

Scroll to Top