Leetcode -- 136. a number that appears only once

subject

Given an array of non-empty 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

---

Own solution

• use set aggregate Storage nums;
• If the addition fails , Then the element already exists in the collection ,remove;
• There is only one element left in the final set ;
• （ The time complexity is O(n), Does not meet the requirements of the topic ）

class Solution {
    
    public int singleNumber(int[] nums) {
    
        int result = -1;
        Set set = new HashSet();
        for (int num : nums){
    
            boolean flag = set.add(num);
            if (flag == false){
    
                set.remove(num);
            }
        }
        for (Object ss : set){
    
            result = (int) ss;
        }
        return result;
    }
}

---

Simple solution

For this question , XOR operation can be used ⊕.

• XOR has three properties
  • Any number and 0 Do exclusive or operations , The result is still the original number , namely a ⊕ 0 = a.
  • Any number is XOR with itself , The result is 0, namely a ⊕ a = 0.
  • XOR operation satisfies the exchange law and the combination law , namely a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a) = b ⊕ 0 = b
• step
  • Let's say there's... In the array 2m+1 Number , Among them is m Two times each , A number appears once .
  • Make a1、a2、…、am For two times m Number ,a (m+1) It's a number that appears once .
  • According to the nature 3, The XOR result of all elements in an array can always be written as follows ：
    (a1⊕a1) ⊕ (a2⊕a2) ⊕ ... ⊕ (am⊕am) ⊕ a(m+1)
  • According to the nature 2 And nature 1, The above formula can be simplified and calculated to obtain the following results ：
    0 ⊕ 0 ⊕ ... ⊕ 0 ⊕ a(m+1) = a(m+1)
  • therefore , The XOR result of all elements in the array is the number that appears only once in the array .

class Solution {
    
    public int singleNumber(int[] nums) {
    
        int single = 0;
        for (int num : nums) {
    
            single ^= num;
        }
        return single;
    }
}