我能想到的方法:
算法:
- 使用哈希表来存储数字及其出现次数
- 遍历数组并增加数字的计数
- 然后遍历哈希表以获取计数为1的数字
你们有没有比这更好的解决方案。需要O(n)的运行时间且不使用额外的空间。
我能想到的方法:
算法:
你们有没有比这更好的解决方案。需要O(n)的运行时间且不使用额外的空间。
XOR
运算符,这是关键所在,因为它具有以下属性:
XOR
是可交换和可结合的(因此执行顺序无关紧要)。XOR
操作将始终为零。XOR
操作将得到该数字。XOR
在一起,所有出现两次的数字都会相互抵消(得到0),而剩下的数字(n
)将与该结果(0)进行XOR
操作,以得到n
。r = 0
for i = 1 to n.size:
r = r xor n[i]
print "number is " + r
不需要哈希表,这个方法具有O(n)的性能和O(1)的额外空间(只使用了一个小整数)。
xor
,或者你的输出有误。你应该提出一个问题,展示你的代码并指明你使用的编程语言。这样,你将得到比仅仅向我提问更广泛的回应。 - paxdiablo在Ruby中的一个答案,假设只有一个单例,其余的恰好出现两次:
def singleton(array)
number = 0
array.each{|n| number = number ^ n}
number
end
irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3
顺便说一下,^是按位异或运算符。异或一切!哈哈哈!
Rampion提醒了我inject方法,所以你可以在一行中完成这个操作:
def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end
array.inject(0) { |accum,number| accum ^ number }
的代码片段。
简述:使用该代码片段对数组进行操作。 - rampiondef singleton(array): return reduce(lambda x,y:x^y, array)
- Adam Rosenfieldsingleton = foldr xor 0
。意思是将列表中的所有元素通过异或运算(xor)合并到一个数值中,最终结果就是这个数值。 - R. Martinho Fernandes解析数组并为数字增加计数。
您可以将其更改为“解析数组,如果该数字已经存在于哈希表中,则从哈希表中删除该数字”。 然后第三步只是“获取仍留在哈希表中的唯一数字”。
给定一个整数数组,除了一个元素之外,每个元素都出现两次。找到那个单独的元素。 我们可以使用异或运算。因为每个数字与自身异或的结果将为零。所以我们对数组中的每个整数进行异或运算,结果就是我们要找的单一元素。 以下是Java版本的代码:
public class Solution {
public int singleNumber(int[] A) {
int res=0;
for(int i=0;i<A.length;i++){
res=res^A[i];
}
return res;
}
}
public class Solution {
public int singleNumber(int[] A) {
int res=0;
int[] count=new int[32];
for(int i=0;i<32;i++){
for(int j=0;j<A.length;j++){
if(((A[j]>>i)&1)==1){
count[i]=count[i]+1;
}
}
if((count[i]%3)!=0){
res=res|(1<<i);
}
}
return res;
}
}
我正在借鉴Michael Sofaer的答案,并在Python和C中重新实现:
Python:
def singleton(array):
return reduce(lambda x,y:x^y, array)
C:
int32_t singleton(int32_t *array, size_t length)
{
int32_t result = 0;
size_t i;
for(i = 0; i < length; i++)
result ^= array[i];
return result;
}
以下是Python中的解决方案,相比Ruby版本更小(并且在我看来更易读):
singleton = lambda x: reduce(operator.xor, x)
Python 3.1 解决方案:
>>> from collections import Counter
>>> x = [1,2,3,4,5,4,2,1,5]
>>> [value for value,count in Counter(x).items() if count == 1 ][0]
3
>>>
arr = get_weird_array()
hash = {}
for number in arr:
if not number in hash:
hash[number] = 1
else:
del hash[number]
for key in hash:
print key
del hash[number]
。 - Seth算法2: