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

矫情吗；* 2024-05-24 01:01 62阅读 0赞

## 1、题目： ##

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
说明：  
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？  
示例 1:

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

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

## 2、解法 ##

第一种：暴力法

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

第二种：使用异或运算来解决，相同的元素异或计算后为0，以示例1为例(简化以8位来存储)，s的二进制位0000 0010，nums\[1\]=0000 0010，异或后s=0000 0000，再和nums\[2\]=0000 0001进行异或后为0000 0001。

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

第三种：使用关联容器存储每个元素（key），元素个数记为value，然后遍历map，获取map中值为1的元素。

class Solution {
        
    public:
    	int singleNumber(vector<int>& nums) {
        
    		unordered_map<int, int> count;
    		int result = 0;
    		for(int i = 0; i < nums.size(); i ++){
        
    		    count[nums[i]] ++;
    		}
    		unordered_map<int, int>::iterator it = count.begin();
    		for(; it != count.end(); it ++){
        
    		    if(it->second == 1) result = it->first;
    		}
    		return result;
    	}
    };

第四种：快速排序

class Solution {
        
    public:
        int singleNumber(vector<int>& nums) {
        
            int i,cur;
            int len=nums.size();
    
            sort(nums.begin(),nums.end());//进行快速排序，得到例如1，1，3，3，2
    
            for(i=0;i<len;i=i+2)//每次后移两个位置
            {
        
                cur=nums[i];
                if(i==len-1)  //如果遍历到最后一个元素,说明该元素为single number
                    return cur;
                if(cur!=nums[i+1])//如果当前元素不等于后一个元素即为single number
                    return cur;
            }
            return -1;
        }
    };