【practise】只出现一次的数字

简介: 【practise】只出现一次的数字

现在给你一个数组,里面放了一些数字,里面都是两两成对,只有一个数字是单独的,要求找出其中只出现一次的数字。相必这道题是非常简单了,有很多解法比如说用暴力求解?比如说用位运算?甚至说用哈希数组统计?

相信大家都有很多方法去解决这个简单的问题,在本文中我收录了三道比较简单的关于“只出现一次的数字”话题的三道题目,我均用位运算的方法去解决,有需要借鉴即可。

1.只出现一次的数字1

题目链接:LINK

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        // 异或思路
        /*
        * 原理:
        * 两个相同的数字相异或为0
        * 0异或上任何数字都为任何数字
        * 异或支持交换律
        */
        int ret = 0;
        for(auto& n: nums)
        {
            ret^=n;
        }
        return ret;
    }
};

上面这道题非常简单,我不再多说。

接下来上一点点难度。

2.只出现一次的数字2

题目链接:LINK

看到这个题目是不是感觉直接位运算不行了?直接位运算的确不行,但是我们到比特位的视角仍然是可以滴。

这个题目之前是写过博客的,详细情况去直接看我写的那个博客文章吧:链接是LINK

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        // 以比特位为单位,对每个数据进行遍历
        for(int i = 0; i < 32; i++)
        {
            int count = 0;
            // 统计所有数字第i位有多少个1
            for(auto& n: nums)
            {
                if(((n >> i) & 1) == 1)
                {
                    count++;
                }
            }
            // 如果这个1的个数模3刚好剩下一个,那么我们的ret也是要有1的。
            if(count % 3 == 1)
            {
                ret = (ret | (1 << i)); 
            }
        }
        return ret;
    }
};

好,倘若你可以独立完成这道题,当然是第一次做的话,说明你的思维贼好使。我们继续来看下面这道题:

3.只出现一次的数字3

题目链接:LINK

这个思路就是把所有数字异或起来,最后得到一个数,这个数其实等价于恰好出现一次的那两个数相异或的结果。我们找到这个数有1的地方,说明两个要返回的数字对应位置的比特位是不一样的。然后我们再根据这个不一样的比特位让所有数分成两组,对每组单独异或就可得到两个要求的数字。

注:上图来源于力扣官方题解。

按照思路,我们可以写出下面代码:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 找出两个不同数的最右的差异为1
        int t_ret = 0;
        for(auto& n: nums)
        {
            t_ret^=n;
        }
        int l = t_ret & (-t_ret);
        // 根据差异我们将所有数字归为两类,一类是一位有1的,另一类是没1的。
        int ret1 = 0;
        int ret2 = 0;
        for(int& n : nums)
        {
            if(n & l)
            {
                ret1 ^= n;
            }
            else
            {
                ret2 ^= n;
            }
        }
        return {ret1, ret2};
    }
};

然后…

原因在于:

所以我们在分组之气做一个判断就行了:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        // 找出两个不同数的最右的差异为1
        int t_ret = 0;
        for(auto& n: nums)
        {
            t_ret^=n;
        }
        
        // 特殊情况:溢出问题,因为INT_MAX所表示的数字比INT_MIN少一个!此时取符号会溢出
        int l = (t_ret == INT_MIN ? t_ret : t_ret & (-t_ret));
        // 根据差异我们将所有数字归为两类,一类是一位有1的,另一类是没1的。
        int ret1 = 0;
        int ret2 = 0;
        for(int& n : nums)
        {
            if(n & l)
            {
                ret1 ^= n;
            }
            else
            {
                ret2 ^= n;
            }
        }
        return {ret1, ret2};
    }
};

4.总结

在上面三道题中我们都用了位运算的思路去做,第一道是比较常规的,第二道是需要理解比特位、位运算才可以想得到,第三道感觉是有点难度的,我就没想到…看的题解~


EOF

相关文章
|
2月前
|
移动开发 vr&ar 数据安全/隐私保护
no-strings-attached-入土为安的第十一天
no-strings-attached-入土为安的第十一天
27 0
|
2月前
|
存储 算法 C语言
【practise】电话号码的字母组合
【practise】电话号码的字母组合
|
C语言 C++
PAT (Basic Level) Practice (中文)1099 性感素数(20分)
“性感素数”是指形如 (p, p+6) 这样的一对素数。之所以叫这个名字,是因为拉丁语管“六”叫“sex”(即英语的“性感”)。(原文摘自 http://mathworld.wolfram.com/SexyPrimes.html) 现给定一个整数,请你判断其是否为一个性感素数。
133 0
PAT甲级 1005. Spell It Right(20分)
PAT甲级 1005. Spell It Right(20分)
53 0
PAT (Basic Level) Practice (中文) 1036 跟奥巴马一起编程 (15 分) p89
PAT (Basic Level) Practice (中文) 1036 跟奥巴马一起编程 (15 分) p89
159 0
|
安全
HDU-1039,Easier Done Than Said?(字符串处理)
HDU-1039,Easier Done Than Said?(字符串处理)
【1013】Battle Over Cities (25 分)
【1013】Battle Over Cities (25 分) 【1013】Battle Over Cities (25 分)
111 0
零元学Expression Design 4 - Chapter 3 看小光被包围了!!如何活用「Text On Path」设计效果
原文:零元学Expression Design 4 - Chapter 3 看小光被包围了!!如何活用「Text On Path」设计效果 本章将教大家如何活用「Text On Path」,做出文绕图以及...
1042 0
零元学Expression Design 4 - Chapter 6 教你如何在5分钟内做出文字立体感效果
原文:零元学Expression Design 4 - Chapter 6 教你如何在5分钟内做出文字立体感效果 又来一篇五分钟做设计啦~ 本篇将教大家如何运用Design内建工具Blend Paths...
1029 0