首页 > 试题广场 >

异或和

[编程题]异或和
  • 热度指数：1087 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

小sun非常的喜欢数字，现在他想到了一个新问题：给你一个数列，想你帮他算算，这个数列中，出现次数为奇数个的数字的异或和。


输入描述:
第一行是一个整数n
接下来一行，n个整数a_i，代表整个数列


输出描述:
一行，代表出现次数为奇数个的数字的异或和
示例1

输入

5
1 2 3 4 4

输出

0
示例2

输入

5
1 1 2 3 3

输出

2

备注:
数据范围：


注意数据较大，cin会T掉
算法知识视频讲解
添加回答
Go
牛客203596504号头像 牛客203596504号
这道题考异或和的特性，以及流式处理。

如果我们试图按题面来做，很快会发现，内存限制存不下原数组。
那桶计数呢？又发现值域也非常大，内存限制也存不下桶数组。

但我们注意到，异或和有这三个性质：
，意味着我们可以任意调整数字的顺序
，意味着我们可以任意调整优先级
 和 ，意味着两个相同的数对于异或和可以当它不存在
有了这些性质，意味着我们可以对数组玩“消消乐”了
出现偶数次的数字全都消没了，出现奇数次的数字只剩下1个。
于是，题目要求的，实际就是整个数组的异或和。
这就意味着我们不需要保存数组，读一个数字处理一个，内存限制问题解决。

代码如下： 
func main() {
	defer writer.Flush()
	n := readInt()
	ans := 0
	for i := 0; i < n; i++ {
		ans ^= readInt()
	}
	writeInt(ans)
}

发表于 2026-04-23 02:48:55 回复(0)
提交观点

问题信息

难度：
1条回答 6浏览

热门推荐

相关试题

异或和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号