力扣每日一题136：只出现一次的数字-CSDN博客

题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。

示例 1

输入nums = [2,2,1]
输出1

示例 2

输入nums = [4,1,2,1,2]
输出4

示例 3

输入nums = [1]
输出1

提示

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某个元素只出现一次以外其余每个元素均出现两次。

通过次数

975.3K

提交次数

1.3M

通过率

72.8%

思路和题解

思路一暴力枚举

每次从数组中取出一个数然后从剩余的数中查找如果找不到就说明这个数只出现一次。时间复杂度On^2,空间复杂度O1时间复杂度不符合要求

思路二排序

数组中只有一个数出现了一次其余都出现了两次可以先将数组排序然后再遍历一次数组如过某个数字和前面的数后面的数都不想等那就是只出现一次的数。时间复杂度O(nlog n),空间复杂度O(1),空间复杂度符合条件时间复杂度不知道不知道算不算线性。

思路三建立映射表

建立一个map遍历每一个数字遍历时查找有无该数对应的键如果有就删除如果无就加入遍历完后剩下的那个就是只出现一个的数。

思路四位运算

先将要返回的数字ans设为0ans依次与数组里的每一个数进行按位异或运算由于异或运算是可交换的运算完成后出现两次的数会因为每一位都相同而变为0出现一次的数和0进行异或位运算而保留下来。时间复杂度O(n),空间复杂度O(1)都符合要求。代码

class Solution{
public:
    int singleNumber(vector<int>& nums)
    {
        int ans=0;
        for(int i=0;i<nums.size();i++)
        ans^=nums[i];
        return ans;
    }
};