LeetCode 136. 只出现一次的数字（巧用位运算）

淡淡的烟草味﹌ 2021-11-13 23:36 340阅读 0赞

### 题目： ###

题目地址：[https://leetcode-cn.com/problems/single-number/][https_leetcode-cn.com_problems_single-number]

**问题描述：**

> 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
> 
> 说明：
> 
> 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
> 
> 示例 1:
> 
> 输入: \[2,2,1\]  
> 输出: 1  
> 示例 2:

### 我的解题思路： ###

#### 1.暴力解法 ####

这种做法很简单，但是肯定是性能很差的一种做法，代码就不写了。

1.  遍历整个数组的所有元素
2.  如果某个数字是第一次出现，加入List
3.  如果某个数字已经在List中，删除它
4.  剩下的数字就是唯一的只出现一次的数字

##### 复杂度分析： #####

时间复杂度：for循坏+从List中查找，时间复杂度是O(n2)

空间复杂度：需要额外的List，空间复杂度是O(n)

#### 2.巧用异或运算 ####

异或运算的规则是：如果不同就得1，如果相同则得0。利用这个特性，遍历异或整个数组的所有元素，那么出现次数为偶数的数字经过异或后等于0，剩下的数字即是数组中只出现一次的数字。

利用异或运算只需要一次for循坏，并且不需要额外的空间。

public static int singleNumber(int[] nums) {
        
        int result = 0;
        //使用异或运算，出现次数为偶数的数字经过异或后等于0，剩下的数字即是数组中只出现一次的数字
        for (int num : nums) {
        
            result = result ^ num;
        }
        return result;
      
    }

### 网上其他题解中可以学习的思路： ###

#### 1. 利用HashMap： ####

**用哈希表避免每次查找元素是否存在需要的 O(n)时间。查找性能比使用List更好。**

class Solution {
        
        public int singleNumber(int[] nums) {
        
            Map<Integer, Integer> map = new HashMap<>();
            for (Integer i : nums) {
        
                Integer count = map.get(i);
                count = count == null ? 1 : ++count;
                map.put(i, count);
            }
            for (Integer i : map.keySet()) {
        
                Integer count = map.get(i);
                if (count == 1) {
        
                    return i;
                }
            }
            return -1; // can't find it.
        }
    }

[https_leetcode-cn.com_problems_single-number]: https://leetcode-cn.com/problems/single-number/