剑指offer--数组中数字出现的次数Ⅱ

题目：

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

示例 1：

输入：nums = [3,4,3,3]
输出：4

思路1：本题跟上一题的出现次数还不相同，上次的是每个数字出现了两次，找出现一次的那个数字，所以可以使用依次相异或的方法，最后的结果就是要找的数。但是这一道题有三个相同的数，没有办法使用异或，但是依然可以使用数位相加的方法，将所有数的二进制数的每一位都相加，最后每一位和3求余，得到的结果就是出现一次的数的二进制数，因为出现三次的数二进制的那一位是相同的，可以找一个数看一下。思路一的时间复杂度是O（N）,空间因为是开了一个固定的数组，是O（1）,效率还是不太高，另一种思路还没太懂。

第一步是计算出来二进制的每一位，通过循环遍历相加的方法，但是这里得到的数组和原数是相反的。

第二步是每位求余，通过或和左移位的方式回复原值。

代码：

#数位计算，将所有数的二进制数的每一位都相加，
        #相同的数对应的二进制数肯定出现了三次，最后将每一位对3取余得到的就是我们要找的二进制数
        #根据数字的范围，最大是32位，所以开一个32位的数组来存储每一位对应出现的次数
        count=[0]*32
        #进行原数组的遍历，得到各位出现1的次数
        #一个数和1相与，可以得到最右位，例如2，0010&0001，得到0说明最右位是0，右移一位之后，0001&0001得到1，说明倒数第二位是1
        for i in range(0,len(nums)):
            for j in range(0,32):
                count[j]+=nums[i]&1
                nums[i]=nums[i]>>1#右移一位计算每位的次数
        #求出来每一位和3求余之后的1的次数，但是注意是反过来的数组，第一个位置记录的是数字的最右边
        res=0
        for i in range(0,32):
            #将数组中的每一位还原回来，可以自己找个二进制试试
            res<<=1
            res|=count[31-i]%3       
        return res

思路二：collections.counter或者map哈希表，但是大家都会写

思路三：有限状态自动机，下次研究

最后

以上就是友好鞋垫为你收集整理的剑指offer--数组中数字出现的次数Ⅱ的全部内容，希望文章能够帮你解决剑指offer--数组中数字出现的次数Ⅱ所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。