只出现一次的数字算法(leetcode第136题)

题目描述：

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

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

 

示例 1 ：

输入：nums = [2,2,1]
输出：1
示例 2 ：

输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：

输入：nums = [1]
输出：1

算法一：hash表

思路：

用hash表记录数出现的次数，之后遍历一次，查找次数为1的数，输出

易错点：nums[i]可能出现负数，但arr下标不能为负数，故要进行讨论

代码实现：

int singleNumber(int* nums, int numsSize) {
    int arr[200000]={0};//hash表
    int i;
    for(i=0;i<numsSize;i++){
        if(nums[i]<0) arr[nums[i]+10000]++;//负数下标，让负数向右偏移10000(防止覆盖原正数)
        else arr[nums[i]]++;
    }
    for(i=0;i<numsSize;i++){
        //分正负讨论
        if(nums[i]<0){
            //只出现一次-->跳出循环
            if(arr[nums[i]+10000]==1) break;
        }
        else{
            if(arr[nums[i]]==1) break;
        }
        
    }
    return nums[i];
}

算法二：位运算

思路：

0和任何数异或运算得到那个数本身

相同的两个数做异或运算得0

偶次会消掉，只留下奇次

代码实现：

int singleNumber(int* nums, int numsSize) {
    int ret=0;
    for(int i=0;i<numsSize;i++) ret^=nums[i];
    return ret;
}