Leetcode 0136. numbers that appear only once: XOR

【LetMeFly】136. A number that appears only once ： Exclusive or

Force button topic link ：https://leetcode.cn/problems/single-number/

Given a Non empty An array of integers , Except that an element only appears once , Each of the other elements occurs twice . Find the element that only appears once .

explain ：

Your algorithm should have linear time complexity . Can you do this without using extra space ？

Example 1:

 Input : [2,2,1]
 Output : 1

Example  2:

 Input : [4,1,2,1,2]
 Output : 4

Method 1 ： Exclusive or

Important properties of XOR ：

1. $a\oplus b\oplus b=a$
2. $0\oplus a=a$
3. The XOR result is independent of the XOR order

therefore , We use it $0$ Start , XOR every number , The end result is the answer .

（ Except that the answer appeared twice ,$0$ An XOR counts twice or $0$; The answer only appears once ,$0$ The XOR answer once equals the answer ）

• Time complexity $O(n)$, among $n$ It's the number of elements
• Spatial complexity $O(1)$

AC Code

C++

class Solution {
    
public:
    int singleNumber(vector<int>& nums) {
    
        int ans = 0;
        for (int& t : nums) {
    
            ans ^= t;
        }
        return ans;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125978508