剑指 Offer 56 - II. 数组中数字出现的次数 II + 位运算

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

Offer_56_2

题目详情

剑指 Offer 56 - II. 数组中数字出现的次数 II + 位运算

解题思路

剑指 Offer 56 - II. 数组中数字出现的次数 II + 位运算
剑指 Offer 56 - II. 数组中数字出现的次数 II + 位运算

java代码

package com.walegarrett.offer;

/**
 * @Author WaleGarrett
 * @Date 2021/2/10 13:43
 */

/**
 * 题目描述:在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
 */
public class Offer_56_2 {
    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums){
            for(int i=0; i<32; i++){
                counts[i] += (num&1);
                num >>>=1;//>>>表示无符号右移
            }
        }
        int ans=0, m=3;
        for(int i=0; i<32; i++){
            ans <<= 1;
            ans |= (counts[31-i] % m);
        }
        return ans;
    }
}

复杂度分析

  • 时间复杂度 O(N) : 其中 N 位数组 nums 的长度;遍历数组占用 O(N) ,每轮中的常数个位运算操作占用 O(1) 。
  • 空间复杂度 O(1) : 数组 counts 长度恒为 32 ,占用常数大小的额外空间。

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

上一篇:第56天学习打卡(初识Mysql及安装)


下一篇:C语言编程练习56:彩票