letcode刷题n6-q136：只出现一次的数字

这是我参与11月更文挑战的第12天，活动详情查看：2021最后一次更文挑战

题目描述

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

说明：

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

示例 1:

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

输入: [4,1,2,1,2]
输出: 4
通过次数532,440提交次数740,226

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
复制代码

思路 & CODE

1. 暴力循环

直接双重for循环，内循环结束还没找到相同的数字就return外层循环的值

public int singleNumber(int[] nums) {
    outer: for (int i = 0; i < nums.length; i++) {
        if (i == nums.length - 1) {
            return nums[i];
        }
        for (int j = 0; j < nums.length; j++) {
            if (j == i) {
                continue;
            }
            if (nums[i] == nums[j]) {
                continue outer;
            }
        }
        return nums[i];
    }
    return 0;
}
复制代码

但是不用想也知道，时间复杂度是O(n^2)

2. 哈希

虽然题目说不能开辟额外空间，但是尝试一下总没错。

创建一个hashMap，每次把数字作为key，出现次数作为value放到map里，最后遍历map的key，返回value为1的key就可以。

public int singleNumber2(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i : nums) {
        map.put(i, map.getOrDefault(i, 0) + 1);
    }
    for (Integer s : map.keySet()) {
        if (map.get(s) == 1) {
            return s;
        }
    }
    return 0;
}
复制代码

3. 位运算

神奇的解法，先有位运算才有这道题！

首先来复习下位运算

在二进制下

• 数字相同为0，不同为1
• 0 ^ 0 = 0
• 0 ^ 1 = 1
• 1 ^ 1 = 0

在十进制下

• 任何数字与0位运算都等于本身
• 任何数字与自身位运算等于0

在这道题中，总共有奇数个数字，去掉一个只出现一次的数字，其他的数字一起做异或运算，结果就为0，然后和只出现一次的数字做位运算，结果就为那个只出现一次的数字。代码也十分简洁：

public int singleNumber3(int[] nums) {
    int num = 0;
    for (int i : nums) {
        num ^= i;
    }
    return num;
}
复制代码