LeetCode 【136. 只出现一次的数字】要是看不懂，我就去出家

写在前面：

如果您觉得写得还可以，那就来关注在下的微信公众号吧“张氏文画”，不光有新鲜的 LeetCode 题解（多种思路，包教包会，开拓思维），还有经典的文章及短视频和大家分享，一起嘿嘿嘿
图片说明

题目描述：

Given an array of integers, every element appears twice except for one. Find that single one.

Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

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

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

难度等级：

Easy

测试样例：

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

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

思路一（位运算）：

二进制异或。两位相同为0，不同得1。即两个数相同，异或得0。0和任何数异或得到的都是该数本身。将数组中所有数进行异或，其中出现两次的数抵消为0，剩下的就是出现一次的那个数。

代码：

时间复杂度O(n)，空间复杂度O(1)

class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int res = 0;
        for (int x : nums) {
            res ^= x;
        }
        return res;
    }
}

Result：

Runtime：1ms

Your runtime beats 99.60% of java submissions.

思路二（快排）：

先排序，每相邻两位相等，不等则输出

代码：

时间复杂度O(n log(n))，空间复杂度O(1)

class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[nums.length - 1];
    }
}

Result：

Runtime：6ms

Your runtime beats 32.32% of java submissions.

思路三（数学）：

观察如下数学公式，可以获得思路

2∗(a+b+c)−(a+a+b+b+c)=c

因此，我们可以开辟 set 来存储去重之后的所有元素并求和得到 set_sum，2倍的 set_sum 减去所有元素的和即为所求值。

代码：

时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int sum_all = 0, set_sum = 0;
        Set<Integer> set = new HashSet<Integer>();

        for (int i = 0; i < nums.length; i++) {
            sum_all += nums[i];
            set.add(nums[i]);
        }
        for (int x : set) {
            set_sum += x;
        }
        return 2 * set_sum - sum_all;
    }
}

Result：

Runtime：7ms

Your runtime beats 30.21% of java submissions.

思路四（哈希）：

哈希集有个重要特性，即不包含任何重复元素的无序集合。所以，对于此题是相当适用的，毕竟我们要求的值就是唯一的。

故当我们向哈希集添加元素时，先检查，如果有了直接移除掉；否则，添加新元素，最后剩下的就是唯一的元素。

注意：Java 中的 Set 集合，无法像 list 一样根据索引获取数据

代码：

时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public int singleNumber(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }

        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                set.remove(nums[i]);
            } else {
                set.add(nums[i]);
            }
        }
        // Java 中 Set 集合中无法像 list 一样根据索引获取数据
        return set.iterator().next();
    }
}

Result：

Runtime：15ms

Your runtime beats 14.57% of java submissions.

大佬们，记得随手关注下我的公众号哦！，一起嘿嘿嘿
图片说明

------至所有正在努力奋斗的程序猿们！加油！！
有码走遍天下 ***寸步难行
1024 - 梦想，永不止步!
爱编程不爱Bug
爱加班不爱黑眼圈
固执但不偏执
疯狂但不疯癫
生活里的菜鸟
工作中的大神
身怀宝藏，一心憧憬星辰大海
追求极致，目标始于高山之巅
一群怀揣好奇，梦想改变世界的孩子
一群追日逐浪，正在改变世界的极客
你们用最美的语言，诠释着科技的力量
你们用极速的创新，引领着时代的变迁

——乐于分享，共同进步，欢迎留言讨论
——Treat Warnings As Errors
——Any comments greatly appreciated
——Talking is cheap, show me the code
——微信公众号：张氏文画