刷题--数组中只出现一次的数字
程序员文章站
2022-07-15 12:21:43
...
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
第一想法是用哈希表,但其实浪费了空间。
我们可以利用异或运算的特性,任何一个数字异或自己都等于0。先考虑如果一个数组中只有一个数字只出现一次,那么只要从头到尾依次异或数组中的每一个数字就能得到那个只出现了一次的数字。在这个问题里,我们可以把原始数组分成两个子数组,使得每个子数组包含一个只出现一次的数字。由于这两个数肯定不一样,所以数组中所有数字的异或结果至少有一位为1,记录下第一个为1的位置,按照这个位置是否为1将数组分成两部分。
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
num = array[0]
for item in array[1:]:
num = num ^ item
index = 0
while not num & 1:
num = num >> 1
index += 1
a, b = 0, 0
for item in array:
temp = item
for _ in range(index):
temp = temp >> 1
if temp & 1:
a = a ^ item
else:
b = b ^ item
return [a, b]
上一篇: 页面渲染及跳转
下一篇: LeetCode 682 棒球比赛
推荐阅读
-
PHP查找数组中只出现一次的数字实现方法【查找特定元素】
-
在字符串中找出第一个只出现一次的字符。经典C语言例题
-
leadcode的Hot100系列--136. 只出现一次的数字
-
python(leetcode)-136只出现一次的数字
-
LeetCode 面试题56 - I. 数组中数字出现的次数
-
在一个非降序排列的数组中,找出数字target出现的次数问题解答
-
JS算法题之查找数字在数组中的索引位置
-
剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III
-
位运算 -- 只出现一次的的数字
-
【知识迁移能力】数组中只出现一次的数字