找奇葩 Python计算
程序员文章站
2022-03-18 21:52:46
在一个长度为 n 的正整数序列中,所有的奇数都出现了偶数次,只有一个奇葩奇数出现了奇数次。你的任务就是找出这个奇葩。输入格式:输入首先在第一行给出一个正整数 n(≤104),随后一行给出 n 个满足题面描述的正整数。每个数值不超过 105,数字间以空格分隔。输出格式:在一行中输出那个奇葩数。题目保证这个奇葩是存在的。输入样例:1223 16 87 233 87 16 87 233 23 87 233 16输出样例:233作者单位代码长度限制时间限制内存限制...
在一个长度为 n 的正整数序列中,所有的奇数都出现了偶数次,只有一个奇葩奇数出现了奇数次。你的任务就是找出这个奇葩。
输入格式:
输入首先在第一行给出一个正整数 n(≤104),随后一行给出 n 个满足题面描述的正整数。每个数值不超过 105,数字间以空格分隔。
输出格式:
在一行中输出那个奇葩数。题目保证这个奇葩是存在的。
输入样例:
12
23 16 87 233 87 16 87 233 23 87 233 16
输出样例:
233
作者 | 单位 | 代码长度限制 | 时间限制 | 内存限制 |
---|---|---|---|---|
陈越 | 浙江大学 | 16 KB | 400 ms | 64 MB |
解题思路:
本题有三个关键的判断点:
- 这个数是否是奇数,只有奇数才满足奇葩数的特点
- 这个数字出现了几次,如何统计
- 如何判断这个数字出现的是奇数次还是偶数次
对应思路:
- 只有奇数才满足奇葩数的特点,因此可以判断%2的结果,过滤掉偶数。
- 声明一个
dict
,用来存每个数出现的次数。首先用in
判断这个数字在不在dict
中,如果在,直接value+1
,如果不在,新增一个以这个数为key
,value
为1
的键值对 - 因为题给条件已知只有一个奇葩数出现了一次。所以只需要在
dict.keys()
中遍历,拿到key
对应的value
判断value
是否能被2整除,如果不能,那这就是答案啦,输出该key
然后退出程序即可。
AC代码:
n = input() #对应题目给的输入格式,作为占位符,不做他用
ques = list(map(int, input().split())) #获取输入的数字并存入列表中
temp = {} #声明一个字典
for i in ques: #遍历需要求解的列表
if i % 2 == 1: #如果这个数是个奇数(偶数直接忽略):
if i in temp: #再判断这个数是否存在于字典中
temp[i] = temp[i] + 1 #如果存在,值+1
else:
temp[i] = 1 #如果不存在,即本次是第一次出现,新增且值为1
for i in temp.keys(): #遍历字典
if temp[i] % 2 == 1: #判断出现次数是否为奇数
print(i) #打印结果
exit(0) #退出程序
编辑一下,再加一条解法,感谢大佬@C^super提供的思路。
解题思路:
异或运算,相同出0,任何不为0的数与0做异或运算结果都是其本身。因此可以利用这个特性做异或运算除掉出现了偶数次的数字,最后的到结果就是所需要的“奇葩数”
AC代码:
n = input() # 同上,占位符
ques = [i for i in list(map(int, input().split())) if i % 2 == 1] # 列表生成式获取输入的奇数集合
ans = 0 # 初始化ans
for i in ques:
ans ^= i # 与列表中每个元素做异或运算
print(ans) # 输出结果
异或学习参考:
知乎专栏:浅谈Python逻辑运算符 异或xor https://zhuanlan.zhihu.com/p/96147159
本文地址:https://blog.csdn.net/weixin_44289959/article/details/111058253
上一篇: PyCharm中 pip进行升级