提问人：Gulzar 提问时间：6/10/2021 更新时间：6/10/2021 访问量：446
在大小为 n-k 的数组中查找 k 个缺失的元素 [duplicate]
Find k missing elements in array of size n-k [duplicate]
问：
给定 [1， n] 中的唯一整数数组，从数组中取出随机元素，然后对其进行随机洗牌，留下一个大小为nkn-kn-k
我想找到那些最复杂度的整数。k
如果 ，我们可以对数组中的所有元素求和，缺失的元素将是（从 1 到 n 的所有数字的总和）与数组元素的总和之间的差值。k==1n(n+1)/2
我想通过k个方程将这个算法扩展到缺失的元素，但不知道如何构建方程。能做到吗？k
答：
0赞
SomeDude
6/10/2021
#1
让我们假设 a[1]、a[2]、a[3]、....a[n] 是原始唯一整数，b[1]， b[2],...b[n-k] 是去掉 k 个整数后的整数。
对数组 a 和 b 进行排序。
对于 b 中的每个相邻对 （i，i+1），在数组 'a' 中对 b[i]， b[i+1] 进行二进制搜索，并得到索引，比如 p、q
如果 q ！= p + 1，则数组 a 中 p、q 之间的所有整数都在去掉的 k 个整数中。
复杂度应为 O（n log n ）
评论
0赞
Gulzar
6/10/2021
我应该澄清一下，这被认为是无效的，就像原始算法可以通过排序来解决，但求和给出.这也不能回答这个问题。k=1o(n)
1赞
SomeDude
6/10/2021
如果您只是在方程式之后，那么评论中共享的链接应该是您的答案。
0赞
user3386109
6/10/2021
@Gulzar计算需要乘法。那么问题来了，哪个更大或.这忽略了求解变量方程所需的时间。它还忽略了您需要使用 bignum 库来计算总和的事实。因此，对输入进行排序并寻找差距是唯一明智的答案。sum(i: [1..N]) i**k for all k: [1..K])O(N * K**2)logNK**2KK
-1赞
user58697
6/10/2021
#2
是的，它可以。不过它并不漂亮。
您需要意识到，在一定范围内[1, n]
- 平方和为
n(n + 1)(2n + 1) / 6 - 立方体的总和为
n**2(n + 1)**2 / 4 - 等
魔鬼在等。幂求和的一般公式是k
Sum(i: [1..n]) i**k = 1/(k+1) Sum(j: [1..k]) (-1)**j binom(k+1, j) Bj n**(k-j+1)
伯努利的数字在哪里。它是 th 次多项式。Bjk+1
伯努利数是出了名的难以计算，由此产生的方程组也不太好处理。
假设您克服了所有计算问题，则复杂性将是 。O(nk)
评论
0赞
Gulzar
6/10/2021
方程可以解吗？如果是，请解释如何。
0赞
Gulzar
6/11/2021
如果它无法解决，我认为这不可能是一个解决方案
评论