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

Categories:

题目描述
思路分析
1. 解法一：位计数（推荐）
相似题目

题目描述

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

思路分析

解法一：位计数（推荐）

核心思路：

统计每一位 1 的出现次数。

若某位出现次数对 3 取模为 1，则该位属于只出现一次的数。

通过重建二进制得到答案。

复杂度分析：

时间复杂度：O(32 * n)，其中 n 表示数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                if (((num >> i) & 1) == 1) {
                    count++;
                }
            }
            if (count % 3 == 1) {
                res |= (1 << i);
            }
        }
        return res;
    }
}

func singleNumber(nums []int) int {
	res := 0
	for i := 0; i < 32; i++ {
		count := 0
		for _, num := range nums {
			if (num>>i)&1 == 1 {
				count++
			}
		}
		if count%3 == 1 {
			res |= 1 << i
		}
	}

	return res
}

相似题目

题目	难度	考察点
136. 只出现一次的数字	简单	位运算
137. 只出现一次的数字 II	中等	位运算
260. 只出现一次的数字 III	中等	位运算
287. 寻找重复数	中等	位运算
389. 找不同	简单	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/83315855