[LeetCode] 137. Single Number II 单独数 II

2021年09月15日 阅读数:2
这篇文章主要向大家介绍[LeetCode] 137. Single Number II 单独数 II,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.html

Note:java

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?python

Example 1:git

Input: [2,2,3,2]
Output: 3

Example 2:github

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

 解法:参考app

Java:post

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}  

Python:url

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        x1, x2, mask = 0, 0, 0
        for i in nums:
            x2 ^= x1 & i;
            x1 ^= i;
            mask = ~(x1 & x2);
            x2 &= mask;
            x1 &= mask;
        return x1  

C++:code

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < nums.size(); ++i) {
            two |= one & nums[i];
            one ^= nums[i];
            three = one & two;
            one &= ~three;
            two &= ~three;
        }
        return one;
    }
};

C++:htm

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int i = 0; i < nums.size(); ++i) {
            b = (b ^ nums[i]) & ~a;
            a = (a ^ nums[i]) & ~b;
        }
        return b;
    }
};

  

  

 

 

相似题目:

[LeetCode] 136. Single Number 单独数

[LeetCode] 260. Single Number III 单独数 III

 

All LeetCode Questions List 题目汇总