【刷题笔记9.24】LeetCode：只出现一次的数字

LeetCode：只出现一次的数字

一、题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

二、分析

如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法（我个人想到使用的是HashMap存储）

对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。

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

三、上代码

方法一：（使用HashMap存储key为元素x，value为次数）

public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            if (map.containsKey(x)) {
                int value  = map.get(x) + 1;
                map.put(x, value);
            } else {
                map.put(x, 1);
            }
        }

        for (int x : map.keySet()) {
            if (map.get(x) == 1) {
                return x;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法二：使用异或

• a ^ a = 0;
• 0 ^ a = a;

public int deal(int[] nums) {
        int single = 0;

        for (int x : nums) {
            single ^= x;
        }
        return single;
    }
1
2
3
4
5
6
7
8