You have an array in which every number is repeated odd number of times (but more than single occurrence). Exactly one number appears once. How do you find the number that appears only once?
您有一个数组，其中每个数字都重复奇数次(但不止一次出现)。只有一个数字出现一次。你如何找到只出现一次的数字?
e.g.: {1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3}
The answer is 9.
答案是9。
I was thinking about having a hash table and then just counting the element whose count is 1. This seems trivial and i am not using the fact that every other element is repeated an odd no of times. Is there a better approach.
我考虑的是哈希表，然后计算元素的计数是1。这看起来很琐碎，我并没有使用任何其他元素都重复一个奇数次的事实。有更好的方法吗?
6 个解决方案
#1
38
I believe you can still use the basic idea of XOR to solve this problem in a clever fashion.
我相信你仍然可以用XOR的基本思想来巧妙地解决这个问题。
First, let's change the problem so that one number appears once and all other numbers appear three times.
首先，让我们改变问题，让一个数字出现一次，所有其他数字出现三次。
Algorithm:
算法:
Here A is the array of length n:
这里A是长度为n的数组:
int ones = 0;
int twos = 0;
int not_threes, x;
for (int i=0; i<n; ++i) {
x = A[i];
twos |= ones & x;
ones ^= x;
not_threes = ~(ones & twos);
ones &= not_threes;
twos &= not_threes;
}
And the element that occurs precisely once is stored in ones. This uses O(n) time and O(1) space.
而恰好发生的元素存储在一个元素中。它使用O(n)时间和O(1)空间。
I believe I can extend this idea to the general case of the problem, but possibly one of you can do it faster, so I'll leave this for now and edit it when and if I can generalize the solution.
我相信我可以把这个想法扩展到这个问题的一般情况，但可能你们中的一个人可以做得更快，所以我现在就把这个留给你们，在我可以推广这个解决方案的时候再编辑它。
Explanation:
解释:
If the problem were this: "one element appears once, all others an even number of times", then the solution would be to XOR the elements. The reason is that x^x = 0, so all the paired elements would vanish leaving only the lonely element. If we tried the same tactic here, we would be left with the XOR of distinct elements, which is not what we want.
如果问题是这样的:“一个元素出现一次，所有其他元素都是偶数次”，那么解决方案将是XOR元素。原因是,x ^ = 0,所以所有成对的元素会消失只留下孤独的元素。如果我们在这里尝试相同的策略，我们将会留下一些不同元素的XOR，这不是我们想要的。
Instead, the algorithm above does the following:
相反，上面的算法如下:
-
onesis the XOR of all elements that have appeared exactly once so far - 一个是所有元素的XOR，这些元素到目前为止只出现过一次。
-
twosis the XOR of all elements that have appeared exactly twice so far - twos是迄今为止出现过两次的所有元素的XOR。
Each time we take x to be the next element in the array, there are three cases:
每次我们把x作为数组中的下一个元素，有三个例子:
- if this is the first time
xhas appeared, it is XORed intoones - 如果这是第一次出现x，它就会被转换成x。
- if this is the second time
xhas appeared, it is taken out ofones(by XORing it again) and XORed intotwos - 如果这是第二次出现x，那么它就会被取出(再次使用XORing)，并将其转换为twos。
- if this is the third time
xhas appeared, it is taken out ofonesandtwos. - 如果这是第三次出现x，它就会从1和2中取出。
Therefore, in the end, ones will be the XOR of just one element, the lonely element that is not repeated. There are 5 lines of code that we need to look at to see why this works: the five after x = A[i].
因此，最终，将会是一个元素的XOR，而不是重复的孤独元素。我们需要查看5行代码来了解为什么这样做:x = A[i]之后的5行代码。
If this is the first time x has appeared, then ones&x=ones so twos remains unchanged. The line ones ^= x; XORs x with ones as claimed. Therefore x is in exactly one of ones and twos, so nothing happens in the last three lines to either ones or twos.
如果这是第一次出现x，那么x和x= 1，所以2保持不变。直线1 = x;XORs x和1的声明。因此，x恰好是1和2中的一个，所以最后三行中的任何一个都不会发生。
If this is the second time x has appeared, then ones already has x (by the explanation above), so now twos gets it with the line twos |= ones & x;. Also, since ones has x, the line ones ^= x; removes x from ones (because x^x=0). Once again, the last three lines do nothing since exactly one of ones and twos now has x.
如果这是第二次x出现，那么已经有x了(根据上面的解释)，所以现在twos得到的是twos |= 1和x;自的x,线的^ = x;删除x的(因为x ^ x = 0)。再一次，最后三行什么都不做，因为只有1和2现在有x。
If this is the third time x has appeared, then ones does not have x but twos does. So the first line let's twos keep x and the second adds x to ones. Now, since both ones and twos have x, the last three lines remove x from both.
如果这是第三次出现x，那么就没有x，而是2。所以第一行，让我们两个保持x，第二个增加x。现在，因为两个和两个都有x，最后的三条线把x从两个中移开。
Generalization:
概括:
If some numbers appear 5 times, then this algorithm still works. This is because the 4th time x appears, it is in neither ones nor twos. The first two lines then add x to ones and not twos and the last three lines do nothing. The 5th time x appears, it is in ones but not twos. The first line adds it to twos, the second removed it from ones, and the last three lines do nothing.
如果一些数字出现5次，那么这个算法仍然有效。这是因为第4次x出现时，它既不是1也不是2。前两行将x加到1，而不是2，最后3行不行。第5次x出现时，是1次，而不是2次。第一行将它添加到twos，第二个行将它从一个删除，最后三行不做任何操作。
The problem is that the 6th time x appears, it is taken from ones and twos, so it gets added back to ones on the 7th pass. I'm trying to think of a clever way to prevent this, but so far I'm coming up empty.
问题是第6次x出现时，它是从1和2中取的，所以它在第7次的时候被加回1。我试着想出一个聪明的方法来阻止它，但到目前为止我是空的。
#2
21
For the problem as stated it is most likely that the most efficient answer is the O(n) space answer. On the other hand, if we narrow the problem to be "All numbers appear n times except for one which only appears once" or even "All numbers appear a multiple of n times except for one which only appears once" then there's a fairly straightforward solution for any n (greater than 1, obviously) which takes only O(1) space, which is to break each number into bits and then count how many times each bit is turned on and take that modulo n. If the result is 1, then it should be turned on in the answer. If it is 0, then it should be turned off. (Any other answer shows that the parameters of the problem did not hold). If we examine the situation where n is 2, we can see that using XOR does exactly this (bitwise addition modulo 2). We're just generalizing things to do bitwise addition modulo n for other values of n.
对于这个问题，很可能最有效的答案是O(n)空间的答案。另一方面,如果我们缩小问题”所有数字出现n次除了一只出现一次“甚至”所有数字出现的n倍除了一只出现一次“还有一个相当简单的解决方案对于任何n(大于1,很明显),只需要O(1)的空间,这是每个数字分解成碎片,然后计算每一位多少次打开模n。如果结果是1,那就应该在答案中打开。如果它是0，那么它应该被关闭。(任何其他答案都表明问题的参数没有保留)。如果我们检查n = 2的情况，我们可以看到使用XOR确实是这样的(位加模2)。我们只是泛化一些东西，对n的其他值进行逐位加模n。
This, by the way, is what the other answer for n=3 does, it's actually just a complex way of doing bit-wise addition where it stores a 2-bit count for each bit. The int called "ones" contains the ones bit of the count and the int called "twos" contains the twos bit of the count. The int not_threes is used to set both bits back to zero when the count reaches 3, thus counting the bits modulo 3 rather than normally (which would be modulo 4 since the bits would wrap around). The easiest way to understand his code is as a 2-bit accumulator with an extra part to make it work modulo 3.
顺便说一下，这是n=3的另一个答案，它实际上只是一个复杂的方法，在这里它存储了2位的计数。int被称为“ones”，其中包含了count的值，而int被称为“twos”，包含了count的两个部分。当计数达到3时，int not_threes被用来将两个位都设为零，因此，计算的是3而不是通常的比特(这将是模块化的，因为比特会被环绕)。理解他的代码最简单的方法是将其作为一个2位累加器，额外的部分使其工作模块化。
So, for the case of all numbers appearing a multiple of 3 times except the one unique number, we can write the following code for 32 bit integers:
因此，对于所有数字出现3次的情况，除了唯一的数字，我们可以为32位整数编写下面的代码:
int findUnique(int A[], int size) {
// First we set up a bit vector and initialize it to 0.
int count[32];
for (int j=0;j<32;j++) {
count[j] = 0;
}
// Then we go through each number in the list.
for (int i=0;i<size;i++) {
int x = A[i];
// And for each number we go through its bits one by one.
for (int j=0;j<32;j++) {
// We add the bit to the total.
count[j] += x & 1;
// And then we take it modulo 3.
count[j] %= 3;
x >>= 1;
}
}
// Then we just have to reassemble the answer by putting together any
// bits which didn't appear a multiple of 3 times.
int answer = 0;
for (int j=31;j>=0;j--) {
answer <<= 1;
if (count[j] == 1) {
answer |= 1;
}
}
return answer;
}
This code is slightly longer than the other answer (and superficially looks more complex due to the additional loops, but they're each constant time), but is hopefully easier to understand. Obviously, we could decrease the memory space by packing the bits more densely since we never use more than two of them for any number in count. But I haven't bothered to do that since it has no effect on the asymptotic complexity.
这段代码略长于另一个答案(由于附加的循环，表面看起来更复杂，但它们都是常数时间)，但希望更容易理解。显然，我们可以更密集地打包，从而减少内存空间，因为在计数中，我们从不使用超过两个字节。但我懒得这么做，因为它对渐近的复杂度没有影响。
If we wish to change the parameters of the problem so that instead the numbers are repeated 5 times, we just change the 3s to 5s. Or we can do likewise for 7, 11, 137, 727, or any other number (including even numbers). But instead of using the actual number, we can use any factor of it, so for 9, we could just leave it as 3, and for even numbers we can just use 2 (and hence just use xor).
如果我们想要改变问题的参数，让数字重复5次，我们就把3s改为5s。或者我们也可以做7、11、137、727或任何其他数字(包括偶数)。但是我们不用实际的数字，我们可以用它的任何因数，所以对于9，我们可以把它当作3，对于偶数我们可以用2(也就是用xor)
However, there is no general bit-counting based solution for the original problem where a number can be repeated any odd number of times. This is because even if we count the bits exactly without using modulo, when we look at a particular bit, we simply can't know whether the 9 times it appears represents 3 + 3 + 3 or 1 + 3 + 5. If it was turned on in three different numbers which each appeared three times, then it should be turned off in our answer. If it was turned on in a number which appeared once, a number which appeared three times, and a number which appeared five times, then it should be turned on in our answer. But with just the count of the bits, it's impossible for us to know this.
然而，对于一个数字可以重复奇数次的原始问题，没有一般的基于比特计数的解决方案。这是因为，即使我们完全不使用模量来计算，当我们观察一个特定的比特时，我们也不知道它的9倍是否代表3 + 3 + 3或1 + 3 + 5。如果它是由三个不同的数字，每个出现三次，那么它应该在我们的答案中被关闭。如果一个数字出现了，一个数字出现了三次，一个数字出现了五次，那么在我们的回答中它应该被打开。但是，只要数一数，我们就不可能知道这些。
This is why the other answer doesn't generalize and the clever idea to handle the special cases is not going to materialize: any scheme based on looking at things bit by bit to figure out which bits should be turned on or off does not generalize. Given this, I don't think that any scheme which takes space O(1) works for the general case. It is possible that there are clever schemes which use O(lg n) space or so forth, but I would doubt it. I think that the O(n) space approach is probably the best which can be done in the problem as proposed. I can't prove it, but at this point, it's what my gut tells me and I hope that I've at least convinced you that small tweaks to the "even number" technique are not going to cut it.
这就是为什么其他的答案不能一概而论，而处理特殊情况的聪明想法也不会成为现实:任何一种基于一点一点地观察事物的计划，都是不可能实现的。考虑到这一点，我不认为任何以空间O(1)为例的方案都适用于一般情况。有可能有使用O(lgn)空间的巧妙方案，但我对此表示怀疑。我认为，O(n)空间方法可能是在问题中所能做的最好的方法。我无法证明这一点，但在这一点上，我的直觉告诉我，我希望我至少已经说服你，对“甚至是数字”技术的细微调整并不能解决问题。
#3
2
I know that the subtext of this question is to find an efficient or performant solution, but I think that the simplest, readable code counts for a lot and in most cases it is more than sufficient.
我知道这个问题的潜台词是找到一种高效的或高性能的解决方案，但我认为最简单的、可读的代码非常重要，在大多数情况下，它是绰绰有余的。
So how about this:
所以这个怎么样:
var value = (new [] { 1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3, })
.ToLookup(x => x)
.Where(xs => xs.Count() == 1)
.First()
.Key;
Good old LINQ. :-)
美好的LINQ。:-)
#4
0
Test Score 100% with c#
测试分数100%与c#。
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
Dictionary<int, int> dic =new Dictionary<int, int>();
foreach(int i in A)
{
if (dic.ContainsKey(i))
{
dic[i]=dic[i]+1;
}
else
{
dic.Add(i, 1);
}
}
foreach(var d in dic)
{
if (d.Value%2==1)
{
return d.Key;
}
}
return -1;
}
}
#5
0
Java, Correctness 100%, Performance 100%, Task score 100%
Java，正确性100%，性能100%，任务评分100%。
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.HashMap;
class Solution {
/*Simple solution
Will be using HashMap(for performance) as Array,
only Key set is needed.
Initially tried with ArryList but there was performance issue with
that so switch to HashMap.
Iterate over the given array and if item is there in key set
remove it(coz you found your pair) otherwise add as new Key.
After full Iteration only one key will be there in the Map that is
your solution.
In Short: If pair is found, remove it from Map's Key set,
Last Key will be your solution
*/
public int solution(int[] A) {
//Map but used as Array
final HashMap<Integer, Boolean> mapHave = new HashMap<>();
//Iterate over given Array
for (int nIdx = 0; nIdx < A.length; nIdx++) {
//Current Item
Integer nVal = A[nIdx];
//Try to remove the current item, if item does not exists will
//return null and if condition will be true
if (mapHave.remove(nVal) == null) {
//current item not found, add it
mapHave.put(nVal, Boolean.TRUE);
}
}
//There will be only one key remaining in the Map, that is
//your solution
return mapHave.keySet().iterator().next();
}
}
#6
-1
Test Score 100% in Python
在Python中测试分数100%。
def solution(A):
n = len(A)
if(A is None or n == 0):
return 0
if(n == 1):
return A[0]
result = 0
for i in range(0, n):
result ^= A[i]
return result
#1
38
I believe you can still use the basic idea of XOR to solve this problem in a clever fashion.
我相信你仍然可以用XOR的基本思想来巧妙地解决这个问题。
First, let's change the problem so that one number appears once and all other numbers appear three times.
首先，让我们改变问题，让一个数字出现一次，所有其他数字出现三次。
Algorithm:
算法:
Here A is the array of length n:
这里A是长度为n的数组:
int ones = 0;
int twos = 0;
int not_threes, x;
for (int i=0; i<n; ++i) {
x = A[i];
twos |= ones & x;
ones ^= x;
not_threes = ~(ones & twos);
ones &= not_threes;
twos &= not_threes;
}
And the element that occurs precisely once is stored in ones. This uses O(n) time and O(1) space.
而恰好发生的元素存储在一个元素中。它使用O(n)时间和O(1)空间。
I believe I can extend this idea to the general case of the problem, but possibly one of you can do it faster, so I'll leave this for now and edit it when and if I can generalize the solution.
我相信我可以把这个想法扩展到这个问题的一般情况，但可能你们中的一个人可以做得更快，所以我现在就把这个留给你们，在我可以推广这个解决方案的时候再编辑它。
Explanation:
解释:
If the problem were this: "one element appears once, all others an even number of times", then the solution would be to XOR the elements. The reason is that x^x = 0, so all the paired elements would vanish leaving only the lonely element. If we tried the same tactic here, we would be left with the XOR of distinct elements, which is not what we want.
如果问题是这样的:“一个元素出现一次，所有其他元素都是偶数次”，那么解决方案将是XOR元素。原因是,x ^ = 0,所以所有成对的元素会消失只留下孤独的元素。如果我们在这里尝试相同的策略，我们将会留下一些不同元素的XOR，这不是我们想要的。
Instead, the algorithm above does the following:
相反，上面的算法如下:
-
onesis the XOR of all elements that have appeared exactly once so far - 一个是所有元素的XOR，这些元素到目前为止只出现过一次。
-
twosis the XOR of all elements that have appeared exactly twice so far - twos是迄今为止出现过两次的所有元素的XOR。
Each time we take x to be the next element in the array, there are three cases:
每次我们把x作为数组中的下一个元素，有三个例子:
- if this is the first time
xhas appeared, it is XORed intoones - 如果这是第一次出现x，它就会被转换成x。
- if this is the second time
xhas appeared, it is taken out ofones(by XORing it again) and XORed intotwos - 如果这是第二次出现x，那么它就会被取出(再次使用XORing)，并将其转换为twos。
- if this is the third time
xhas appeared, it is taken out ofonesandtwos. - 如果这是第三次出现x，它就会从1和2中取出。
Therefore, in the end, ones will be the XOR of just one element, the lonely element that is not repeated. There are 5 lines of code that we need to look at to see why this works: the five after x = A[i].
因此，最终，将会是一个元素的XOR，而不是重复的孤独元素。我们需要查看5行代码来了解为什么这样做:x = A[i]之后的5行代码。
If this is the first time x has appeared, then ones&x=ones so twos remains unchanged. The line ones ^= x; XORs x with ones as claimed. Therefore x is in exactly one of ones and twos, so nothing happens in the last three lines to either ones or twos.
如果这是第一次出现x，那么x和x= 1，所以2保持不变。直线1 = x;XORs x和1的声明。因此，x恰好是1和2中的一个，所以最后三行中的任何一个都不会发生。
If this is the second time x has appeared, then ones already has x (by the explanation above), so now twos gets it with the line twos |= ones & x;. Also, since ones has x, the line ones ^= x; removes x from ones (because x^x=0). Once again, the last three lines do nothing since exactly one of ones and twos now has x.
如果这是第二次x出现，那么已经有x了(根据上面的解释)，所以现在twos得到的是twos |= 1和x;自的x,线的^ = x;删除x的(因为x ^ x = 0)。再一次，最后三行什么都不做，因为只有1和2现在有x。
If this is the third time x has appeared, then ones does not have x but twos does. So the first line let's twos keep x and the second adds x to ones. Now, since both ones and twos have x, the last three lines remove x from both.
如果这是第三次出现x，那么就没有x，而是2。所以第一行，让我们两个保持x，第二个增加x。现在，因为两个和两个都有x，最后的三条线把x从两个中移开。
Generalization:
概括:
If some numbers appear 5 times, then this algorithm still works. This is because the 4th time x appears, it is in neither ones nor twos. The first two lines then add x to ones and not twos and the last three lines do nothing. The 5th time x appears, it is in ones but not twos. The first line adds it to twos, the second removed it from ones, and the last three lines do nothing.
如果一些数字出现5次，那么这个算法仍然有效。这是因为第4次x出现时，它既不是1也不是2。前两行将x加到1，而不是2，最后3行不行。第5次x出现时，是1次，而不是2次。第一行将它添加到twos，第二个行将它从一个删除，最后三行不做任何操作。
The problem is that the 6th time x appears, it is taken from ones and twos, so it gets added back to ones on the 7th pass. I'm trying to think of a clever way to prevent this, but so far I'm coming up empty.
问题是第6次x出现时，它是从1和2中取的，所以它在第7次的时候被加回1。我试着想出一个聪明的方法来阻止它，但到目前为止我是空的。
#2
21
For the problem as stated it is most likely that the most efficient answer is the O(n) space answer. On the other hand, if we narrow the problem to be "All numbers appear n times except for one which only appears once" or even "All numbers appear a multiple of n times except for one which only appears once" then there's a fairly straightforward solution for any n (greater than 1, obviously) which takes only O(1) space, which is to break each number into bits and then count how many times each bit is turned on and take that modulo n. If the result is 1, then it should be turned on in the answer. If it is 0, then it should be turned off. (Any other answer shows that the parameters of the problem did not hold). If we examine the situation where n is 2, we can see that using XOR does exactly this (bitwise addition modulo 2). We're just generalizing things to do bitwise addition modulo n for other values of n.
对于这个问题，很可能最有效的答案是O(n)空间的答案。另一方面,如果我们缩小问题”所有数字出现n次除了一只出现一次“甚至”所有数字出现的n倍除了一只出现一次“还有一个相当简单的解决方案对于任何n(大于1,很明显),只需要O(1)的空间,这是每个数字分解成碎片,然后计算每一位多少次打开模n。如果结果是1,那就应该在答案中打开。如果它是0，那么它应该被关闭。(任何其他答案都表明问题的参数没有保留)。如果我们检查n = 2的情况，我们可以看到使用XOR确实是这样的(位加模2)。我们只是泛化一些东西，对n的其他值进行逐位加模n。
This, by the way, is what the other answer for n=3 does, it's actually just a complex way of doing bit-wise addition where it stores a 2-bit count for each bit. The int called "ones" contains the ones bit of the count and the int called "twos" contains the twos bit of the count. The int not_threes is used to set both bits back to zero when the count reaches 3, thus counting the bits modulo 3 rather than normally (which would be modulo 4 since the bits would wrap around). The easiest way to understand his code is as a 2-bit accumulator with an extra part to make it work modulo 3.
顺便说一下，这是n=3的另一个答案，它实际上只是一个复杂的方法，在这里它存储了2位的计数。int被称为“ones”，其中包含了count的值，而int被称为“twos”，包含了count的两个部分。当计数达到3时，int not_threes被用来将两个位都设为零，因此，计算的是3而不是通常的比特(这将是模块化的，因为比特会被环绕)。理解他的代码最简单的方法是将其作为一个2位累加器，额外的部分使其工作模块化。
So, for the case of all numbers appearing a multiple of 3 times except the one unique number, we can write the following code for 32 bit integers:
因此，对于所有数字出现3次的情况，除了唯一的数字，我们可以为32位整数编写下面的代码:
int findUnique(int A[], int size) {
// First we set up a bit vector and initialize it to 0.
int count[32];
for (int j=0;j<32;j++) {
count[j] = 0;
}
// Then we go through each number in the list.
for (int i=0;i<size;i++) {
int x = A[i];
// And for each number we go through its bits one by one.
for (int j=0;j<32;j++) {
// We add the bit to the total.
count[j] += x & 1;
// And then we take it modulo 3.
count[j] %= 3;
x >>= 1;
}
}
// Then we just have to reassemble the answer by putting together any
// bits which didn't appear a multiple of 3 times.
int answer = 0;
for (int j=31;j>=0;j--) {
answer <<= 1;
if (count[j] == 1) {
answer |= 1;
}
}
return answer;
}
This code is slightly longer than the other answer (and superficially looks more complex due to the additional loops, but they're each constant time), but is hopefully easier to understand. Obviously, we could decrease the memory space by packing the bits more densely since we never use more than two of them for any number in count. But I haven't bothered to do that since it has no effect on the asymptotic complexity.
这段代码略长于另一个答案(由于附加的循环，表面看起来更复杂，但它们都是常数时间)，但希望更容易理解。显然，我们可以更密集地打包，从而减少内存空间，因为在计数中，我们从不使用超过两个字节。但我懒得这么做，因为它对渐近的复杂度没有影响。
If we wish to change the parameters of the problem so that instead the numbers are repeated 5 times, we just change the 3s to 5s. Or we can do likewise for 7, 11, 137, 727, or any other number (including even numbers). But instead of using the actual number, we can use any factor of it, so for 9, we could just leave it as 3, and for even numbers we can just use 2 (and hence just use xor).
如果我们想要改变问题的参数，让数字重复5次，我们就把3s改为5s。或者我们也可以做7、11、137、727或任何其他数字(包括偶数)。但是我们不用实际的数字，我们可以用它的任何因数，所以对于9，我们可以把它当作3，对于偶数我们可以用2(也就是用xor)
However, there is no general bit-counting based solution for the original problem where a number can be repeated any odd number of times. This is because even if we count the bits exactly without using modulo, when we look at a particular bit, we simply can't know whether the 9 times it appears represents 3 + 3 + 3 or 1 + 3 + 5. If it was turned on in three different numbers which each appeared three times, then it should be turned off in our answer. If it was turned on in a number which appeared once, a number which appeared three times, and a number which appeared five times, then it should be turned on in our answer. But with just the count of the bits, it's impossible for us to know this.
然而，对于一个数字可以重复奇数次的原始问题，没有一般的基于比特计数的解决方案。这是因为，即使我们完全不使用模量来计算，当我们观察一个特定的比特时，我们也不知道它的9倍是否代表3 + 3 + 3或1 + 3 + 5。如果它是由三个不同的数字，每个出现三次，那么它应该在我们的答案中被关闭。如果一个数字出现了，一个数字出现了三次，一个数字出现了五次，那么在我们的回答中它应该被打开。但是，只要数一数，我们就不可能知道这些。
This is why the other answer doesn't generalize and the clever idea to handle the special cases is not going to materialize: any scheme based on looking at things bit by bit to figure out which bits should be turned on or off does not generalize. Given this, I don't think that any scheme which takes space O(1) works for the general case. It is possible that there are clever schemes which use O(lg n) space or so forth, but I would doubt it. I think that the O(n) space approach is probably the best which can be done in the problem as proposed. I can't prove it, but at this point, it's what my gut tells me and I hope that I've at least convinced you that small tweaks to the "even number" technique are not going to cut it.
这就是为什么其他的答案不能一概而论，而处理特殊情况的聪明想法也不会成为现实:任何一种基于一点一点地观察事物的计划，都是不可能实现的。考虑到这一点，我不认为任何以空间O(1)为例的方案都适用于一般情况。有可能有使用O(lgn)空间的巧妙方案，但我对此表示怀疑。我认为，O(n)空间方法可能是在问题中所能做的最好的方法。我无法证明这一点，但在这一点上，我的直觉告诉我，我希望我至少已经说服你，对“甚至是数字”技术的细微调整并不能解决问题。
#3
2
I know that the subtext of this question is to find an efficient or performant solution, but I think that the simplest, readable code counts for a lot and in most cases it is more than sufficient.
我知道这个问题的潜台词是找到一种高效的或高性能的解决方案，但我认为最简单的、可读的代码非常重要，在大多数情况下，它是绰绰有余的。
So how about this:
所以这个怎么样:
var value = (new [] { 1, 6, 3, 1, 1, 6, 6, 9, 3, 3, 3, 3, })
.ToLookup(x => x)
.Where(xs => xs.Count() == 1)
.First()
.Key;
Good old LINQ. :-)
美好的LINQ。:-)
#4
0
Test Score 100% with c#
测试分数100%与c#。
using System;
using System.Collections.Generic;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A) {
Dictionary<int, int> dic =new Dictionary<int, int>();
foreach(int i in A)
{
if (dic.ContainsKey(i))
{
dic[i]=dic[i]+1;
}
else
{
dic.Add(i, 1);
}
}
foreach(var d in dic)
{
if (d.Value%2==1)
{
return d.Key;
}
}
return -1;
}
}
#5
0
Java, Correctness 100%, Performance 100%, Task score 100%
Java，正确性100%，性能100%，任务评分100%。
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.HashMap;
class Solution {
/*Simple solution
Will be using HashMap(for performance) as Array,
only Key set is needed.
Initially tried with ArryList but there was performance issue with
that so switch to HashMap.
Iterate over the given array and if item is there in key set
remove it(coz you found your pair) otherwise add as new Key.
After full Iteration only one key will be there in the Map that is
your solution.
In Short: If pair is found, remove it from Map's Key set,
Last Key will be your solution
*/
public int solution(int[] A) {
//Map but used as Array
final HashMap<Integer, Boolean> mapHave = new HashMap<>();
//Iterate over given Array
for (int nIdx = 0; nIdx < A.length; nIdx++) {
//Current Item
Integer nVal = A[nIdx];
//Try to remove the current item, if item does not exists will
//return null and if condition will be true
if (mapHave.remove(nVal) == null) {
//current item not found, add it
mapHave.put(nVal, Boolean.TRUE);
}
}
//There will be only one key remaining in the Map, that is
//your solution
return mapHave.keySet().iterator().next();
}
}
#6
-1
Test Score 100% in Python
在Python中测试分数100%。
def solution(A):
n = len(A)
if(A is None or n == 0):
return 0
if(n == 1):
return A[0]
result = 0
for i in range(0, n):
result ^= A[i]
return result