谢谢你这个有趣的问题:

因为你让我想起了牛顿的工作，它真的可以解决这个问题

请参考牛顿恒等式

As变量的数量=方程的数量(必须为一致性)

我认为，对于这个问题，我们应该提高袋数的幂，以便创建不同的方程。

我不知道，但是，我相信如果有一个函数，比如f，我们要加上f(xi)

x1+x2+…+ xk = z1

x12 + x22 + ... + xk2 = z2

............

............

............

x1k + x2k + ... + xkk = XP

休息是一个不确定时间和空间复杂性的数学工作，但牛顿恒等式肯定会发挥重要作用。

我们不能用集合理论吗 .difference_update()或在这个问题方法中是否有线性代数的机会?

你能查一下每个号码是否都存在吗?如果是，你可以试试这个:

S =袋子中所有数字的和(S < 5050) Z =缺失数的和5050 - S

如果缺失的数字是x和y，则:

x = Z - y和 max(x) = Z - 1

所以你检查从1到max(x)的范围，并找到这个数字

我们假设它是一个从1到N的数组，它的元素是a1, a2， ....一个:

1+N=N+1;
2+N-1=N+1;

… 所以这个和是唯一的。我们可以从头到尾扫描数组来添加两个元素。如果和是N+1;好吧，否则它们就不见了。

for (I <= N/2) {
    temp = a[I] + a[n-I];
    if (temp != N+1) then
        Find the missing number or numbers
}

迭代这个循环，很容易就能得到答案。

// Size of numbers
def n=100;

// A list of numbers that is missing k numbers.
def list;

// A map
def map = [:];

// Populate the map so that it contains all numbers.
for(int index=0; index<n; index++)
{
  map[index+1] = index+1;  
}

// Get size of list that is missing k numbers.
def size = list.size();

// Remove all numbers, that exists in list, from the map.
for(int index=0; index<size; index++)
{
  map.remove(list.get(index));  
}

// Content of map is missing numbers
println("Missing numbers: " + map);

非常好的问题。我会用Qk的集合差。很多编程语言甚至都支持它，比如Ruby:

missing = (1..100).to_a - bag

这可能不是最有效的解决方案，但如果我在这种情况下面临这样的任务(已知边界，低边界)，这是我在现实生活中会使用的解决方案。如果数字集非常大，那么我当然会考虑一个更有效的算法，但在此之前，简单的解决方案对我来说已经足够了。

下面是Dimitris Andreou链接的摘要。

记住i次幂的和，其中i=1 2 .. k。这就把问题简化为解方程组

A1 + A2 + ... + AK = B1

A12 + A22 + ... + AK2 = B2

...

a1k + a2k + ... + laas = bk

利用牛顿恒等式，知道bi就可以计算

c1 = a1 + a2 +ak

c2 = a1a2 + a1a3 +，+ ak-1ak

...

ck = a1a2 ..ak

如果你展开多项式(x-a1)…(x-ak)系数正好是c1，…， ck -见Viète的公式。由于每个多项式因子都是唯一的(多项式环是欧几里得域)，这意味着ai是唯一确定的，直到排列为止。

这就证明了记住幂就足以恢复数字。对于常数k，这是一个很好的方法。

However, when k is varying, the direct approach of computing c1,...,ck is prohibitely expensive, since e.g. ck is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp or Cantor-Zassenhaus.

常数k的高级伪代码:

计算给定数的i次幂 相减得到未知数字的i次幂的和。称这些和为bi。 利用牛顿恒等式从bi中计算系数;叫它们ci。c1 = b1;C2 = (c1b1 - b2)/2;详见维基百科的精确公式 因式分解多项式xk-c1xk-1 +…+ ck。 多项式的根是所需的数a1，…正义与发展党。

对于改变k，使用例如Miller-Rabin，找到质数n <= q < 2n，并对所有数字对q进行模数化简来执行步骤。

编辑:这个答案的前一个版本表明，可以使用特征2 (q=2^(log n))的有限域来代替Zq，其中q是素数。但事实并非如此，因为牛顿公式需要除以k以内的数。