首页 > 其他分享 >剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣(LeetCode)

剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣(LeetCode)

时间:2022-10-25 00:33:38浏览次数:89  
标签:力扣 shu nums int Offer II 出现 数字

剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣(LeetCode)

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

思路分析:

每一个数字在某些位上可能是1,也可能是0。因为除一个数字外,其他数字都出现了三次,因此我们可以统计每一位上1总共有多少个,然后对3取模,得到的就是出现一次的数字在该位的值。

方法一:

利用一个32位的数组统计每一位1出现的个数

点击查看代码
class Solution {
public:
    int count[32];
    int singleNumber(vector<int>& nums) {
        for (auto i=nums.begin();i!=nums.end();i++)
        {
            unsigned int num=*i;
            unsigned int res=1;
            //cout<<"------"<<endl;
            for (int j=0;j<32;j++)
            {
                if (res&num){
                    count[j]++;
                    //cout<<j<<endl;
                }
                res<<=1;
            }
        }
        int ans=0;
        for (int i=0;i<32;i++)
        {
            int res=(count[i]%3)<<i;
            ans|=res;
        }
        return ans;
    }
};

时间复杂度O(n*32),空间复杂度O(1),但是该方法的实现效率较低。对于这一类问题:一个数出现m次,其他数均出现n次,都可以用这个方法解决。


方法二:

整体思路同方法一,但是求解次数时,方法一的效率太低,我们可以构造一个有限自动机,然后通过位操作提高效率

具体分析:

  • 我们对某一位进行分析,因为最后答案是对3取模,因此我们可以每次处理完一个数之后,都进行取模。这样的话,每一位可能出现的情况就是:0,1,2 这三种状态之一,开始时,该位为0,然后遍历数组,当遇到1时,转换到下一个状态,当遇到零时,状态不变。

  • 因为我们想要利用位运算,而三种状态是不可能用一位表示的,因此需要用两位表示,这时状态就在 00,01,10 这三个状态之间转换。

  • 我们可以设高位为a,低位为b。

  • 先考虑b,转换情况如下,注意不存在11这种状态:

    b a n ans
    1 0 0 1
    1 1 0 不存在
    0 0 0 0
    0 1 0 0
    0 0 1 1
    0 1 1 0
    1 0 1 0
    1 1 1 不存在

    根据表格可以得到:ans=(~a) b (~n) | (~b) (~a) n=(~a) (b^n)
    综上:b=(~a)(b^n)

  • 我们接着考虑a,a的值不仅与自己和n有关,还与b的新值有关:

    a b n ans
    1 0 0 1
    1 1 0 不存在
    0 1 0 0
    0 0 0 0
    1 0 1 0
    1 1 1 不存在
    0 1 1 0
    0 0 1 1

    可以得到 ans=a(~b) (~n) + (~a) (~b) n=(~b)(a^n);

  • 对每一位都有如上的结果。然后我们考虑如何还原得到出现一次的数,因为该数只出现了一次,因此它的某一位只能是0或者1,不可能出现前面的10这种情况,这种情况只会出现在计算的过程中,在最后的结果中某一位要么是0要么是1.因此要得到这个数,只需要将每一位的b返回即可。

点击查看代码
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a=0;
        int b=0;
        for (auto i=nums.begin();i!=nums.end();i++)
        {
            b=(~a)&(b^(*i));
            a=(~b)&(a^(*i));
        }
        return b;
    }
};

参考链接:

https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/

https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/by-8hasefu1-1mgg/

标签:力扣,shu,nums,int,Offer,II,出现,数字
From: https://www.cnblogs.com/sjw-blogs/p/16822366.html

相关文章

  • 力扣 114. 二叉树展开为链表-原地算法(O(1) 额外空间)详解
    114.二叉树展开为链表给你二叉树的根结点 root ,请你将它展开为一个单链表:展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而......
  • HashSet集合 Array sort方法 学习 剑指offer 练习1
    HashSet集合是基于HashMap来实现的,不允许有重复的元素        允许有NULL值 无序,不会记录插入的顺序HashSet实例化对象  HashSet<Strin......
  • 剑指Offer-14-剪绳子/力扣-343-整数拆分
    对于一段绳子,第一刀下去可以将绳子分成i和n-i两段,其中i的取值范围为[1,n-1]dp[n]表示n可分成的最大乘积和,dp[n]=max(dp[n],max(i*n-i,i*f(n-i)))初始化:全部初始化为1i......
  • IIS 7.5 Application Warm-Up Module
    有些web应用在可以处理用户访问之前,需要装载很多的数据,或做一些花费很大的初始化处理。今天使用ASP.NET的开发人员经常使用应用的Global.asax 文件中......
  • Windows NLB搭配IIS的ARR搭建高可用环境
    在现行的许多网络应用中,有时一台服务器往往不能满足客户端的要求,那么有没有什么办法解决服务器的高可伸缩性、高可用、高可靠性和高性能,提升服务器的SLA?......
  • 亲密接触IIS 8和Web Deploy 3.0
    IIS8是和WindowsServer2012一起发布的。它带来多项有趣的特性,像对NUMA的支持、WebSockets、安全性改进和更好的web部署工具等。IIS8中一项有趣的改进就是​​NUMA感知的......
  • IIS Community Newsletter June 2013
    Announcements​Windows2012ServerR2previewreleasedWindowsServer2012R2providesawiderangeofnewandenhancedfeaturesandcapabilitiesspanningserv......
  • 键盘中上、下、左、右四个光标键所对应的ASCII码值为多少
    首先给出ASCII码值表:   上、下、左、右这四个光标键对应的ASCII码值不是一个值而是三个,准确的说光标键的ASCII码值是一个组合。  每个方向键所对应的三个键值为:0x1b+......
  • 力扣OJ(601-800)
    目录​​621.任务调度器​​​​624.数组列表中的最大距离​​​​625.最小因式分解​​​​630.课程表III​​​​634.寻找数组的错位排列​​​​643.子数组最大平......
  • 记录一次Server 2012R2 安装IIS时,一直提示需要重启
    1.WCF服务中,TCP管道以下(包含TCP管道)的三个选项不要勾选。2…netframework3.5及相关不要勾选,否则会一致提示错误。其他的都可以勾选,然后安装…......