只出现一次的数字

谁借莪１个温暖的怀抱￠ 2022-12-05 10:22 122阅读 0赞

# 只出现一次的数字 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/single-number/

## 2、题目要求 ##

> **题目描述**

给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

> **示例 1:**

输入: [2,2,1]
    输出: 1

> **示例 2:**

输入: [4,1,2,1,2]
    输出: 4

## 3、代码思路 ##

方法一：`Set` 去重

1.  遇到一个元素时，先判断其在不在 `set` 中，如果在 `set` 中，则证明该元素为出现两次的元素，则将其从 `set` 中移除；如果不在 `set` 中则将其添加至 `set` 集合中
2.  当执行完遍历后 `set` 中还剩余一个元素，这个元素就是只出现过一次的元素

--------------------

方法二：异或

不看 `LeetCode` 题解，我真就想不出来还有异或这种骚操作，异或运算有以下三个性质

1.  任何数和 `0` 做异或运算，结果仍然是原来的数，即 `a^0=a⊕0=a`
2.  任何数和其自身做异或运算，结果是 `0`，即 `a^a=a⊕a=0`
3.  异或运算满足交换律和结合律，即 `a^b^a=b^a^a=b^(a^a)=b^0=ba⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。`

解题思路为：

![image-20200909215007678][]

## 4、代码实现 ##

方法一：`Set` 去重

class Solution {
        
        public int singleNumber(int[] nums) {
        
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
        
                if (set.contains(nums[i])) {
        
                    set.remove(nums[i]);
                }
                else{
        
                    set.add(nums[i]);
                }
            }
            int single = 0;
            for (Integer integer : set) {
        
                single = integer;
            }
            return single;
        }
    }

方法二：异或

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

[image-20200909215007678]: /images/20221123/db232dec68e94f03892a3d8b68caaf4c.png