通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            jpress从3.x升级到4.x,显示有些问题,慢慢修复中

leetcode 剑指 Offer 56 - II. 数组中数字出现的次数 II

467人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/869

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 56 - II. 数组中数字出现的次数 II

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

示例 1:

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

示例 2:

输入:nums = [9,1,7,9,7,9,7]
输出:1

难度:中等;标签:无;编程语言:JAVA


我的解法

无,这题不会,看题解方法吧


其它方法1

public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums) {
            for(int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>>= 1;
            }
        }
        int res = 0, m = 3;
        for(int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }

用位运算,把每个数每一位上的0和1记录下来,模3,那些出现3次的就为0,剩下的0,1就是剩余的一个数的(可以找几个数算一下试试就理解了)


其它方法2

public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }

这个位运算不行的估计是看不懂的,我也看不懂,直接看题解吧

面试题56 - II. 数组中数字出现的次数 II(位运算 + 有限状态自动机,清晰图解)

并行位运算,看了原来的式子化简还能懂一些,直接上面的式子完全看不懂,这个原来不会的就算了吧,想不到的,另外所谓的有限状态自动机可以这样理解,就是没有进位等,每一位和其它位都没有关联,只与当前位有关,这样没有关联性,只考虑当前位,解题的难度就降低很多


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告