leetcode.137. 只出现一次的数字 II---三法解决（哈希，位运算，排序）

137. 只出现一次的数字 II

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

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

输入：nums = [0,1,0,1,0,1,99]
输出：99
 

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 

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

题解：

方法一：结构体模拟哈希思想

由于不是正经的哈希表，所以在进行存储后再拿出来时需要两次for循环来遍历。

代码：

struct hash{
    int id;
    int val;
};
int singleNumber(int* nums, int numsSize){
    struct hash*a = (struct hash*)malloc(sizeof(struct hash)*numsSize);
    for(int i=0;i<numsSize;i++){
        a[i].val = 0;
    }
    for(int i=0;i<numsSize;i++){
        a[i].id = nums[i];
        a[i].val++;
    }

    for(int i=0;i<numsSize;i++){
        for(int j=0;j<numsSize;j++){
            if(a[j].id==a[i].id&&i!=j){//单独拉出一个id并求其总次数
                a[i].val++;
            }
        }
        if(a[i].val==1){
            return a[i].id;
        }
    }

    return 1;
}

方法二：使用位运算

我们发现我们要的答案的第i个二进制位要么是0，要么是1，且由于其只出现一次，所以加起来也就是0或1；
而对于非答案，由于它们每一个位可为0，也可为1，所以三个三个加一块后为0或3。
因此我们可以发现：
将所有数的第i位的数字提取出来加在一起除以3后，得到的余数即为答案的第i个二进制位的数。
利用此性质，我们可以使用位运算进行处理：
注意的是在位运算中，对某个数使用 & 1，相当于只考虑最后一个特定的位；
而对一个数对另一个数使用 | ，相当于将第一个数不含有的，第二个数含有的给加到第一个数中。

int singleNumber(int* nums, int numsSize){
    int val = 0;//答案初始每个位都是0
    for(int i=0;i<32;i++){//遍历位
        int sum = 0;//记录所有数的特定位的数的总和
        for(int j=0;j<numsSize;j++){//遍历数组
            sum+= (nums[j]>>i) & 1//每次只考虑最后一个位
        }
        if(sum%3!=0){
            val |= (1u<<i);//给答案填上对应的位的数
        }
        //若余数为0，则此位直接为0，所以不用再赋值了，因为本来就是0
    }
    return val;
}

方法三：排序遍历

直接排序好数组遍历即可。