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

本问题对应的 leetcode 原文链接:剑指 Offer 56 – II. 数组中数字出现的次数 II
对应打卡问题:【位运算专题】剑指 Offer 56 – II. 数组中数字出现的次数 II

问题描述

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

示例 1:

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

示例 2:

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

限制:

  • 1 <= nums.length <= 10000
  • 1 <= nums[i] < 2^31

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public int singleNumber(int[] nums) {
        int[] res = new int[32];
        int m = 1;
        int sum = 0;
        for(int i = 0; i < 32; i++){
            for(int j = 0; j < nums.length; j++){
                if((nums[j] & m) != 0){
                    res[i]++;
                }
            }

            res[i] = res[i] % 3;
            sum = sum + res[i] * m;
            m = m << 1;
        }

        return sum;
    }
}

时间复杂度:O(n)
额外空间复杂度:O(1)

发表回复

后才能评论