Pou*_*ami 21 c arrays algorithm complexity-theory big-o
存在大小为n的数组,并且数组中包含的元素在1和n-1之间,使得每个元素出现一次并且仅一个元素出现多次.我们需要找到这个元素.
虽然这是一个非常常见的问题,但我仍然没有找到合适的答案.大多数建议是我应该将数组中的所有元素相加,然后从中减去所有索引的总和,但如果元素的数量非常大,这将不起作用.它会溢出.关于XOR门的使用也有一些建议dup = dup ^ arr[i] ^ i,我不清楚.
我已经提出了这个算法,这是一个增加算法的增强,并将在很大程度上减少溢出的机会!
for i=0 to n-1
begin :
diff = A[i] - i;
sum = sum + diff;
end
diff包含重复元素,但使用此方法我无法找到重复元素的索引.为此,我需要再次遍历数组,这是不可取的.任何人都可以提出一个更好的解决方案,不涉及添加方法或XOR方法在O(n)中工作？
tem*_*def 61
根据问题描述的限制,您可以通过多种方式考虑此问题.
如果你知道一个元素是重复的,那么有很多方法可以解决这个问题.一个特别聪明的解决方案是使用按位XOR运算符.XOR具有以下有趣的属性:
这里的属性(1)和(2)意味着当获取一组值的XOR时,将XOR应用于元素的顺序无关紧要.您可以根据需要对元素重新排序或分组.属性(3)意味着如果你多次将相同的值一起异或,则返回零,而属性(4)意味着如果你对0的任何异或,则返回原始数字.将所有这些属性组合在一起,就会得到一个有趣的结果:如果你取一组数字的XOR,结果就是组中出现奇数次的所有数字的异或.这样做的原因是,当您将出现偶数次数的XOR组合在一起时,您可以将这些数字的XOR分解为一组对.每对XOR为0乘以(3),并且所有这些零的组合XOR通过(4)返回零.因此,甚至多重性的所有数量都抵消了.
要使用它来解决原始问题,请执行以下操作.首先,将列表中的所有数字进行异或.这给出了出现奇数次的所有数字的XOR,最终是除了重复之外的从1到(n-1)的所有数字.现在,将此值与从1到(n-1)的所有数字的XOR进行异或.然后,这使得先前未被抵消的范围1到(n-1)中的所有数字都抵消,仅留下重复的值.此外,这在O(n)时间内运行并且仅使用O(1)空间,因为所有值的XOR适合单个整数.
在您的原始帖子中,您考虑了一种替代方法,它使用从1到n-1的整数之和为n(n-1)/ 2的事实.但是,您担心这会导致整数溢出并导致问题.在大多数机器上你是对的,这会导致溢出,但是(在大多数机器上)这不是问题,因为算术是使用固定精度整数完成的,通常是32位整数.当发生整数溢出时,得到的数字不是没有意义的.相反,它只是你计算实际结果时得到的值,然后除了最低32位之外的所有内容.从数学上来说,这是被称为模算术,以及在计算机中的操作完成模2 32.但更一般地说,假设整数以k为模数存储,用于某些固定的k.
幸运的是,许多你所知道并且喜欢普通算术的算术法仍然适用于模运算.我们只需要更准确地使用我们的术语.我们说,x是全等y模K(表示为x≡ ķ Y)如果X和Y离开相同的余除以k分配.在物理机器上工作时这很重要,因为当大多数硬件上发生整数溢出时,结果值与模数k的真值一致,其中k取决于字大小.幸运的是,以下定律适用于模运算:
例如:
这意味着如果你想通过查找数组元素的总和并减去预期的总数来计算重复值,即使存在整数溢出,一切都会正常工作,因为标准算法仍会产生相同的值(模k)在硬件中.也就是说,你也可以使用基于XOR的方法,它根本不需要考虑溢出.:-)
如果不能保证只复制一个元素,但是你可以修改元素数组,那么有一个漂亮的算法可以找到重复的值. 这个早期的SO问题描述了如何实现这一目标.直观地说,我们的想法是你可以尝试使用存储桶排序对序列进行排序,其中元素数组本身也被循环使用以保存存储桶的空间.
如果不能保证只复制一个元素,并且无法修改元素数组,那么问题就更难了.这是一个经典(而且很难)面试的问题,据报道,Don Knuth需要24小时才能解决这个问题.诀窍是通过将数组作为函数从数字1-n处理到1-(n-1)然后查找该函数的两个输入来将问题减少到循环查找的实例.然而,最终的算法,称为Floyd的循环寻找算法,非常漂亮和简单.有趣的是,它与用于在线性时间和恒定空间中检测链表中的循环的算法相同.我建议查阅,因为它定期出现在软件访谈中.
有关算法的完整描述以及分析,正确性证明和Python实现,请查看解决此问题的此实现.
希望这可以帮助!