c++怎么判断只出现一次的数字

本篇内容主要讲解“c++怎么判断只出现一次的数字”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“c++怎么判断只出现一次的数字”吧!

目前成都创新互联已为上千家的企业提供了网站建设、域名、虚拟空间、成都网站托管、企业网站设计、定边网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。

算法

位运算异或的使用(一)中,两位相同的数异或为0,转换成3位数的"异或"操作位0,也就是说我们需要实现同一个bit位的3个1,操作为0就可以,将问题转换为对如何实现同一bit位的三个数的操作a?b?c =0的运算。

因为两位数的异或操作,是同一个bit位的两个数的加法,忽略进位的情况,换种说法就是两数相加对2取余数。所以三个相同的数的a?b?c = 0的操作就变成了,三位数操作对3取余了。同样的道理,4位数,n位数都可以采用这一个算法来实现。

题目:只出现一次的数字

算法1:数学公式

这个题目可以转换成下面的公式:2c = 3(a+b+c)-sum,

这里的a,b,c是数组中出现的元素,c是出现了一次的数,a,b都是出现了3次的数。

sum表示的是:数组里面所有数的和。

备注:同样的算法,也适合数组里面有n次重复的数组,和1个不重复的数 ,公式为:n(a+b+c)-sum = (n-1)c

代码实现:

func singleNumber(nums []int) int {    m := make(map[int]int)     s1,s2 := 0,0    for _,n:=range nums {        _,ok := m[n]        if !ok {            m[n] = n        }        s1 += n    }       for _,v:= range m {        s2 += v    }    res := (3*s2-s1)/2    return res}// 算法:假设3个a,b,一个c: 公式: 3(a+b+c) - sum = 2c

算法2: 采用位运算

指导思路是:转换成前面算法篇:位运算异或的使用(一)中,两位相同的数异或为0,转换成3位数的"异或"操作位0,也就是说我们需要实现同一个bit位的3个1,操作为0就可以,将问题转换为对如何实现同一bit位的三个数的操作a?b?c =0的运算。

因为两位数的操作采用的是异或,也就是 :

1^1 = 0 1^0 = 10^1 = 10^0 =0这其实是同一个bit位的两个数的加法,忽略进位的情况,换种说法就是两数相加对2取余数。

所以三个相同的数的a?b?c = 0的操作就变成了,三位数操作对3取余了。

代码实现:

func singleNumber(nums []int) int {    num,res := 0,0    for i:=0;i<64;i++ {        // 每一bit位都需要计算,所以这里要做清0处理        num = 0        for _, n := range nums {            // 通过右移,来计算num的数量            num += (n>>i)&1        }        // 将计算结果还原到对应的bit位        res |= (num)%3< 

到此,相信大家对“c++怎么判断只出现一次的数字”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!


网页标题:c++怎么判断只出现一次的数字
文章转载:http://azwzsj.com/article/jopsgh.html