LeetCode-136. 只出现一次的数字

我就是我 2024-03-27 11:33 64阅读 0赞

#### 目录 ####

*   *  题目分析
     *  哈希集
     *  位运算

题目来源  
[https://leetcode.cn/problems/single-number/][https_leetcode.cn_problems_single-number]

### 题目分析 ###

题目有个条件可谓相当重要，即凡重复的元素最多重复一次（原话：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次）。

### 哈希集 ###

哈希集有个重要特性，其是不包含任何重复元素的无序集合。所以，对于此题可谓是相当适用的，毕竟我们要求的值就是唯一的。  
故当我们向哈希集添加重复元素时，如果添加失败，则移除当前试图向哈希集添加的元素。  
**时间复杂度: O(n) 空间复杂度: O(n)**

class Solution {
        
        public int singleNumber(int[] nums) {
        
            if (nums.length < 1 || nums == null){
        
                return 0;
            }
            HashSet<Integer> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++) {
        
                // 尝试将当前元素加入 set
                if (!set.add(nums[i])){
        
                    // 当前元已经存在于 set，即当前元素第二次出现，从 set 删除
                    set.remove(nums[i]);
                }
            }
            // 最后只剩一个不重复的元素
            return set.iterator().next();
        }
    }

![在这里插入图片描述][7465e093f4904ff79dc0edac593d67e5.png]

### 位运算 ###

**首先复习一下什么是异或运算**  
相同为0，不同为1(也可以这样记，无进位相加)

int a = 7 int b = 13  a^b
    a:00111
    b:01101
    --------
      01010

(1)0^N=N  
(2)N^N=0  
(3)异或运算满足交换律和结合律  
任何数和自己做异或运算，结果为 0，即 a⊕a=0  
任何数和 0 做异或运算，结果还是自己，即 a⊕0=a  
异或运算中，满足交换律和结合律，也就是 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

**拓展一道题就明白了**  
不用额外变量交换数组中两个数的值(根据上面的公式)  
![在这里插入图片描述][90a5a922e7a248da893539408b758e3c.png]  
**时间复杂度: O(n) 空间复杂度: O(1)**

class Solution {
        
        public int singleNumber(int[] nums) {
        
            if (nums.length < 1 || nums == null){
        
                return 0;
            }
            int ans = 0;
            for (int i = 0; i < nums.length; i++) {
        
                ans ^= nums[i];
            }
            return ans;
        }
    }

![在这里插入图片描述][5dcbe8ba088d40a6b7c41a3c87c1990b.png]

[https_leetcode.cn_problems_single-number]: https://leetcode.cn/problems/single-number/
[7465e093f4904ff79dc0edac593d67e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/8c90c3d2e129416dad2ee3999261715a.png
[90a5a922e7a248da893539408b758e3c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1b0138f4a20348e5b4dc48bda939dcef.png
[5dcbe8ba088d40a6b7c41a3c87c1990b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/3488116e77864ea188b49d071b32ae3b.png