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
——微信公众号：张氏文画