只出现一次的数字–力扣

• 2021 年 4 月 3 日
• 筆記
• 算法题目

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

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

示例 1:

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

示例 2:

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

我的解法：
思路：首先对nums数组进行排序，然后判断第 i 个元素和该元素的前后两个元素是否相等，如果跟前后两个元素都不相等，则答案就是该元素。这样解决问题有一个弊端就是，需要考虑数组越界问题。
出现的问题：

1. 第一个元素没有之前的元素，最后一个元素没有之后的元素，所以就需要分情况考虑
2. 所以我就分了三种情况：①当前元素是第一个元素 ②当前元素既不是第一个元素也不是最后一个元素 ③当前元素是最后一个元素
3. 数组的长度为 1 时，应当直接返回这个元素.

    public int singleNumber(int[] nums) {
        Arrays.sort(nums);//对数组进行排序
        int len = nums.length;//数组的长度
        int ans = nums[0];//记录答案，初始化为第 0 号元素的值
        if (len == 1) return ans;//数组长度为1
        for (int i = 0; i < len; i++) {
            //是第一个元素
            if (i == 0 && nums[i]!=nums[i+1]){
            }
            //既不是第一个，也不是最后一个
            if (i != 0 && i != len-1){
                if (nums[i]!=nums[i-1]&&nums[i]!=nums[i+1]){
                    ans = nums[i];
                }
            }
            //最后一个元素
            if (i == len-1 && nums[i] != nums[i-1]){
                ans = nums[i];
            }
        }
        return ans;
    }

看了别人做的后，突然感觉自己真实太傻了！^–

人家的解法：

• 使用异或运算，将所有值进行异或
• 异或运算，相异为真，相同为假，所以 a^a = 0 ;0^a = a
• 因为异或运算 满足交换律 a^b^a = a^a^b = b 所以数组经过异或运算，单独的值就剩下了

class Solution {
    public int singleNumber(int[] nums) {
        int reduce = 0;
        for (int num : nums) {
            reduce =  reduce ^ num;
        }
        return reduce;
    }
}

虽然不知道底层的异或具体怎么实现的，但是这样做太简单了！不用排序，直接将每个元素都进行异或，最后就是答案了！

注意：这样做也是有条件的，必须保证出现重复元素的次数必须是偶数次才能保证这种解法是正确的。恰好改题目说的是除了某个元素只出现一次以外，其余每个元素均出现两次

虽然这道题目比较简单，但是我觉我们应该学会从每道题目中学到一些没见过的、有趣的东西！