可能的重复：
简单的面试问题变得更难：给定数字 1..100，找到缺失的数字
在线性时间和常量空间中查找数组中缺失和重复的元素
我在一个论坛上看到一个有趣的问题。
你有从 1 到 100 的 100 个元素，但由于错误，其中一个数字通过重复自身而与另一个数字重叠。
例如。 1,99,3,...,99,100
数组没有排序，如何找到重复的数字？
我知道哈希可以做到 O(n) 时间和 O(n) 空间，我需要 O(1) 空间。
计算两个和：总和和平方和。
在你的例子中：
sum = 1+99+3...+100
sq_sum = 1^2+99^2+3^2+...+100^2
假设 y 替换了序列中的 x。
sum = n(n+1)/2 -y+x.
sq_sum = n(n+1)(2n+1)/6 -x^2 +y^2
现在，求解 x 和 y。
恒定空间和 O(n) 时间。
如何求解 x 和 y
由方程可知：
x = sum - n(n+1)/2 +y
将其代入第二个方程：
sq_sum = n(n+1)(2n+1)/6 -(sum - n(n+1)/2 +y)^2 +y^2
请注意，y^2 取消，留下一个只有一个未知数的线性方程：y。解决这个问题！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
