And*_*s T 4 arrays algorithm integer unique
我正在寻找一种算法来解决以下问题:我们给出了一个大小为n的整数数组,其中包含k(0 <k <n)个元素恰好一次.每个其他整数在数组中出现偶数次.输出应该是k个唯一数字中的任何一个.k是固定数字,不是输入的一部分.
一个例子是输入[1, 2, 2, 4, 4, 2, 2, 3],1和3都是正确的输出.
最重要的是,算法应该在O(n)时间内运行,并且只需要额外的O(1)空间.
编辑:关于是否只有一个唯一的整数或多个,存在一些混淆.我为此道歉.正确的问题是存在任意但固定的数量.我已经更新了上面的原始问题.
"但丁".对于最多有两个这样的数字的情况给出了一个很好的答案.此链接还提供三种解决方案."David Eisenstat"评论说,任何固定的k都可以做到.我很感激解决方案.
Sum*_*eet 10
有一种标准算法可以使用XOR运算符来解决这些问题:
时间复杂度= O(n)
空间复杂度= O(1)
假设您的输入数组只包含一个奇数次发生的元素,并且偶数发生次数,我们利用以下事实:
当应用xor时,任何具有偶数0和1的任何表达式的任何表达式总是= 0.
那是
0^1^....... = 0 as long as number of 0 is even and number of 1 is even
0和1可以任何顺序发生.
因为所有出现偶数次数的数字都会使它们的相应位形成偶数1和0,并且当我们取数组的所有元素的xor时,只有只发生一次的数字会遗漏它的位.
0(from no's occuring even times)^1(from no occuring once) = 1
0(from no's occuring even times)^0(from no occuring once) = 0
正如你所看到的,只保留了一次出现的数字.
这意味着当给出这样一个数组并且你取所有元素的xor时,结果就是只出现一次的数字.
所以长度为n的数组的算法是:
result = array[0]^array[1]^.....array[n-1]
不同的场景
正如OP提到的那样,输入也可以是一个阵列,其中只有两个数字只出现一次而休息偶数次.
这是使用与上述相同的逻辑解决的,但差别不大.
算法思路:
如果你取所有元素的xor,那么肯定所有元素出现偶数次都将导致0,这意味着:
结果将仅在该位位置处具有位1,其中两个数字的位仅发生一次不同.
我们将使用上述想法.
现在我们关注结果xor位为1(任何位为1)并使其休息为0.结果是一个数字,它允许我们区分两个数字(所需的数字).
因为该位是1,这意味着它们在这个位置不同,这意味着在这个位置有一个0,而一个将有1.这意味着一个数字被采用时AND结果为0而一个没有.
由于设置最右边的位非常容易,我们将结果xor设置为
A = result & ~(result-1)
现在遍历数组一次,如果array [i]&A为0,则将数字存储在变量number_1中
number_1 = number_1^array[i]
除此以外
number_2 = number_2^array[i]
因为剩余的数字偶数次出现,它们的位会自动消失.
所以算法是
1.取所有元素的xor,称之为xor.
2.设置xor的最右边位并将其存储在B中.
3.执行以下操作:
number_1=0,number_2=0;
for(i = 0 to n-1)
{
if(array[i] & B)
number_1 = number_1^array[i];
else
number_2 = number_2^array[i];
}
number_1和number_2是必需的数字.