算法题每日一练—第46天：只出现一次的数字-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、问题描述

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

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

二、题目要求

样例 1

输入: [2,2,1]
输出: 1
复制代码

样例 2

输入: [4,1,2,1,2]
输出: 4
复制代码

考察

1.位运算异或、双指针、数学思想
2.建议用时15~30min
复制代码

三、问题分析

本题是位运算的第1题，没了解过位运算相关知识点可以看这一篇文章：

算法题每日一练—第45天：位运算。

1.双指针

一开始，我想的是先对数组从小到大排序。举两个例子，排序后如下：

1 1 2 2 4
1 2 3 3
两两对比，因为排序后相等的数字都会聚集到一起，假如不相等就输出，OK！
复制代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int i=0,j=1,n=nums.size();//双指针i j
        sort(nums.begin(),nums.end());//排序
        while(i<n&&j<n)
        {
            if(nums[i]!=nums[j])//不相等
            {
                return nums[i];//直接返回结果
            }
            i+=2,j+=2;//向后顺延两个
        }
        return nums[n-1];//输出最后一个
    }
};
复制代码

2.位运算

位运算一开始属实没想到，看了题解之后发现解法十分巧妙。

本题知识点用到了异或，这篇文章有详细的讲解，我就大概说一下。

异或就是相同的两个数字会被消掉，异或运算满足交换律和结合律，比如：

4^1^2^1^2 = 1^1^2^2^4 = 0^0^4 = 4
复制代码

结果就是最后一个没有被消掉的数字。

四、编码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
       int i=0,n=nums.size();//初始化
       for(i=1;i<n;i++)
       {
           nums[i]=nums[i]^nums[i-1];//异或开始
       }
       return nums[n-1];//输出结果
};
复制代码