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

Categories:

题目描述
思路分析
1. 解法一：异或分组（推荐）
相似题目

题目描述

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

思路分析

解法一：异或分组（推荐）

核心思路：

全部异或得到 xor = a ^ b，其中 a、b 为只出现一次的两个数。

取 xor 的最低位 1 作为分组标记，将数组分成两组。

两组分别异或即可得到 a、b。

复杂度分析：

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

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

class Solution {
    public int[] singleNumbers(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }

        int lowbit = xor & -xor;
        int a = 0;
        int b = 0;

        for (int num : nums) {
            if ((num & lowbit) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return new int[]{a, b};
    }
}

func singleNumbers(nums []int) []int {
	xor := 0
	for _, num := range nums {
		xor ^= num
	}

	lowbit := xor & -xor
	a, b := 0, 0

	for _, num := range nums {
		if num&lowbit == 0 {
			a ^= num
		} else {
			b ^= num
		}
	}

	return []int{a, b}
}

相似题目

题目	难度	考察点
136. 只出现一次的数字	简单	位运算
260. 只出现一次的数字 III	中等	位运算
137. 只出现一次的数字 II	中等	位运算
318. 最大单词长度乘积	中等	位运算
剑指 Offer 56 - I. 数组中数字出现的次数	中等	位运算

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/51036818