博客主页：https://tomcat.blog.csdn.net
博主昵称：农民工老王
主要领域：Java、Linux、K8S
期待大家的关注💖点赞👍收藏⭐留言💬

创作申明
本文是一篇针对leetcode算法题的解题博客。我给出的解题思路和代码，以及对优质解答的讲解 均属于原创内容，本文的原创标识也是基于此。而题目全部出自leetcode.cn，优质解答搜索自全网，本文已经标明其引用出处。

我是一个算法初学者，完全的菜鸟，文中的算法题属于入门级别。本文适合算法新手阅读，而对算法大佬没有任何阅读价值

题目

题目链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x21ib6/

题干

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

说明

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

示例 1

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

示例 2

输入：nums = [1,2,3,4]
输出：false

示例 3

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

我的解答

以下是我的解答，虽然能实现，但是没有什么亮点。

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

    for(Integer getKey: hashMap.keySet()){
        if(hashMap.get(getKey)==1){
           int  result = getKey;
           return  result;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public int singleNumber(int[] nums) {
    int numsLength = nums.length;
    //只有一个元素的情况
    if (numsLength == 1) {
        return nums[0];
    }
    //排序
    Arrays.sort(nums);
    //第一个元素的情况
    if (nums[0] != nums[1]) {
        return nums[0];
    }
    //中间的情况
    for (int i = 1; i < numsLength - 2; i++) {
        if (nums[i-1] != nums[i] && nums[i] != nums[i + 1]) {
            return nums[i];
        }
    }
    //最后一个元素情况
    return nums[numsLength - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

优质解答

leetcode网页中，题目下面的第一条讨论（作者力扣id：桂继宏）中提到的答案就非常优质，获得了很多人的点赞和认同。
这位大佬充分利用了异或运算，将所有值进行异或后，得到的值就是最终的答案。

public int singleNumber(int[] nums) {
    int reduce = 0;
    for (int num : nums) {
        reduce =  reduce ^ num;
    }
    return reduce;
}
1
2
3
4
5
6
7

看到这个答案后，就发现我忽略了题目中很关键的信息——“其余每个元素均出现两次”。这是异或运算的基础。我审题时，忽略了“两次”，误以为是“多次”。哎，所以说审题很重要。不过大概率来说，即使我知道是两次，也不一定能想起用位运算。

总之，和大佬的答案相比，我的解答就像一坨屎。此刻我只想对自己说：“老王，这就是差距啊，你要知耻啊！”

---

如需转载，请注明本文的出处：农民工老王的CSDN博客https://blog.csdn.net/monarch91 。