位运算:Leetcode137.只出现一次的数字(2)

2023-12-21 19:08:58

题目描述:

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

示例 1:

输入:nums = [2,2,3,2]
输出:3

示例 2:

输入:nums = [0,1,0,1,0,1,100]
输出:100

思路1:最先想到的肯定是哈希表,两次遍历。第一次遍历求出每个元素出现的次数,第二次遍历找出出现次数为1的元素

tips:map和set里是不允许有重复元素的,就意味着count方法统计元素出现的次数只会返回0或1,这是我第一次犯下的错误,用count==1来判断结果发现怎么都不对。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> mp;
        int ans;
        for(auto num :nums)
        {
            mp[num]++;
        }
        for(auto num :nums)
        {
            if(mp[num]==1)
                {
                    ans=num;
                    break;
                }
        }
        return ans;
    }
};

思路2:利用位运算

我们知道每一位相加的结果无非就下面四种情况

我们要找的数记为ret,所有数该位求和结果%3得到的结果与ret相同,如果结果为1,我们就将该位改为1,如果为0则改为0,最后便能求得要找的数。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret=0;
        for(int i=0;i<32;i++)
        {
            int sum=0;
            for(int x:nums)
            {
                if((x>>i)&1==1)
                    sum++;
            }
            sum%=3;
            if(sum==1)
                ret|=1<<i;
        }
        return ret;
    }
};

?

文章来源:https://blog.csdn.net/m0_73865858/article/details/135136103
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。