如何解决这个问题？这些值是无序的，但都在 [1..n] 范围内。例如数组为 [3,1,2,5,7,8]。答案: 4, 6
我在另一篇类似的帖子中看到了这个解决方案，但我不理解最后一步:
- 计算数字之和S=a1+...+an。
- 计算数字平方之和T=a1²+...+an²。
- 你知道这个和应该是S'=1+...+n=n(n+1)/2
- 你知道这个数字平方和应该是T'=1²+...+n²=n(n+1)(2n+1)/6。
- 现在设置以下方程组 x+y=S'-S, x²+y²=T'-T。
- 通过写出x²+y²=(x+y)²-2xy来求解 => xy=((S'-S)²-(T'-T))/2.
- 现在这些数字只是z的二次方程的根: z²-(S'-S)z+((S'-S)²-(T'-T))/2=0.
为什么要在最后一步中将这个二次方程式设为未知数为z的方程式？这个方程式的解决方案背后的直觉是什么？
这种方法不可取，因为它存在整数溢出问题。所以使用XOR方法来查找这两个数字，它具有高性能。如果你感兴趣我可以解释一下。
根据下面来自@ordinary的请求，我将解释算法：
编辑
假设数组a[]的最大元素是B，即假设a[]={1,2,4}，这里3和5不在a[]中，因此最大元素是B=5。
a中的所有元素进行异或运算得到XB的所有元素进行异或运算得到xx = x &(~(x-1));找到x的最左侧为1的位a[i] ^ x == x，则将a[i]与p进行异或运算，否则与q进行异或运算B的所有k，如果k ^ x == x，则将其与p进行异或运算，否则与q进行异或运算p和q证明：
假设 a = {1,2,4} 且 B 是 5，即从 1 到 5 中缺失的数字为 3 和 5。
当我们对 a 中的元素和从 1 到 5 的数字进行 XOR 运算后，剩余的值为 3 和 5 的异或结果 x。
现在，当我们找到 x 的最左边的位设置时，它实际上就是 3 和 5 中最左边不同的位。（3--> 011，5 --> 101，且 x = 010 其中 x = 3 ^ 5）
接着，我们试图根据 x 的位设置将其分成两组，因此这两个组将是：
p = 2 , 2 , 3 (all has the 2nd last bit set)
q = 1, 1, 4, 4, 5 (all has the 2nd last bit unset)
如果我们对 p 的元素进行 XOR 操作，会得到 3，同样地，如果我们对 q 的所有元素进行 XOR 操作，则会得到 5。因此答案为：
Java 代码如下：
public void findNumbers(int[] a, int B){
int x=0;
for(int i=0; i<a.length;i++){
x=x^a[i];
}
for(int i=1;i<=B;i++){
x=x^i;
}
x = x &(~(x-1));
int p=0, q=0;
for(int i=0;i<a.length;i++){
if((a[i] & x) == x){
p=p^a[i];
}
else{
q=q^a[i];
}
}
for(int i=1;i<=B;i++){
if((i & x) == x){
p=p^i;
}
else{
q=q^i;
}
}
System.out.println("p: "+p+" : "+q);
}
设x和y为一个二次方程的根。
SUM = x + yPRODUCT = x * y如果我们知道根之和与根之积，就可以重建二次方程，即：
z^2 - (SUM)z + (PRODUCT) = 0
你提到的算法中，我们找出和与积，再利用上面的公式重构二次方程。
如果你对详细推导感兴趣，可以参考这里。阅读"从根的和与积重构二次方程"。
Actual Series: 1 2 3 4 5 6 a:sum=21 product= 720
Missing Number series: 1 * 3 4 * 6 b:sum=14 product= 72
a+b=21-14= 7 , ab=720/72=10
a-b= sqrt[(a+b)^2 -4ab]。a-b= 3
a+b=7
a-b=3
将两个方程式相加：
2a=10, a=5
那么b=7-5=2，因此，2和5缺失。
从现在开始
x+y == SUM
xy == PRODUCT
有两种情况。如果 PRODUCT 是零，那么一个数是 0，另一个数是 SUM。否则，两个数都不为零；我们可以通过乘以 x 来改变等式：
x*x + xy == x*SUM
替换第二个方程式：
x*x + PRODUCT = x*SUM
x*x - x*SUM + PRODUCT = 0
因此
x = SUM/2 + sqrt(SUM*SUM - 4*PRODUCT)/2
y = SUM/2 - sqrt(SUM*SUM - 4*PRODUCT)/2
Java实现：（基于@Ben Voigt）
BigInteger fact=1;
int sum=0;
int prod=1;
int x,y; // The 2 missing numbers
int n=a.length;
int max=MIN_VALUE;
for (int i=0; i<a.length;i++){
sum+=a[i]; //sums the existing numbers
prod*=a[i]; //product the existing numbers
if (max<a[i]) //searches for the biggest number in the array
max=a[i];
}
while(max!=1){ //factorial for the maximum number
fact*=max;
max--;
}
sum=(n*(n+1))/2 - sum; //the sum of the 2 missing numbers
prod=fact/prod; //the product of the 2 missing numbers
x=sum/2 + Math.sqrt(sum*sum - 4*prod)/2;
y=sum/2 - Math.sqrt(sum*sum - 4*prod)/2;
public static void main(String args[] ) throws Exception {
Scanner input = new Scanner(System.in);
System.out.println("Enter no. of students in the class");
int N = input.nextInt();
List<Integer> l = new ArrayList<Integer>();
int Nn=N;
System.out.println("Enter the roll numbers");
for(int i=0;i<Nn;i++)
{
int enter=input.nextInt();
l.add(enter);
}
Collections.sort(l);
Integer listarr[]=new Integer[l.size()];
listarr =l.toArray(listarr);
int check=0;
int m1[]=new int[N];
for(int i=0;i<N;i++)
{
m1[i]=i+1;
}
for (int i = 0; i < N; i++) {
boolean flag=false;
{
for (int j = 0; j < listarr.length; j++) {
if(m1[i]==listarr[j])
{
flag=true;
break;
}
else
{
flag=false;
}
}
if(flag==false)
{
System.out.println("Missing number Found : " + m1[i]);
}
}
}
#include <iostream>
#include<math.h>
using namespace std;
int main()
{
int i,x[100],sum1=0,sum2=0,prod1=1,prod2=1,k,j,p=0;
cout<<"Enter 8 elements less than 10, they should be non recurring"<<endl;
for(i=0;i<8;i++)
{
cin>>x[i];
}
sum1=((10)*(11))/2;
for(i=0;i<8;i++)
{
sum2+=x[i];
}
k=sum1-sum2;
for(i=1;i<10;i++)
{
prod1=prod1*i;
}
for(i=0;i<8;i++)
{
prod2=prod2*x[i];
}
j=prod1/prod2;
p=sqrt((k*k)-(4*j));
cout<<"One missing no:"<<p/2<<endl;
cout<<"Second missing no:"<<k-p/2<<endl;
}
#include <stdio.h>
#include <math.h>
/*
the sum should be 1+...+n = n(n+1)/2
the sum of squares should be 1^2+...+n^2 = n(n+1)(2n+1)/6.
*/
void find_missing_2_numbers(int *arr, int n);
int main()
{
int arr[] = {3,7,1,6,8,5};
find_missing_2_numbers(arr, 8);
return 0;
}
void find_missing_2_numbers(int *arr, int n)
{
int i, size, a, b, sum, sum_of_sqr, a_p_b, as_p_bs, a_i_b, a_m_b;
size = n - 2;
sum = 0;
sum_of_sqr = 0;
for (i = 0; i < size; i++)
{
sum += arr[i];
sum_of_sqr += (arr[i] * arr[i]);
}
a_p_b = (n*(n+1))/2 - sum;
as_p_bs = (n*(n+1)*(2 * n + 1))/6 - sum_of_sqr;
a_i_b = ((a_p_b * a_p_b) - as_p_bs ) / 2;
a_m_b = (int) sqrt((a_p_b * a_p_b) - 4 * a_i_b);
a = (a_p_b + a_m_b) / 2;
b = a_p_b - a;
printf ("A: %d, B: %d\n", a, b);
}
Below is the generic answer in java code for any number of missing numbers in a given array
//assumes that there are no duplicates
a = [1,2,3,4,5]
b = [1,2,5]
a-b=[3,4]
public list<integer> find(int[] input){
int[] a= new int[] {1,2,3,4,5};//create a new array without missing numbers
List<Integer> l = new ArrayList<Integer>();//list for missing numbers
Map<Integer,Integer> m = new HashMap<Integer>();
//populate a hashmap with the elements in the new array
for(int i=0;i<input.length;i++){
m.put(input[i], 1);
}
//loop through the given input array and check for missing numbers
for(int i=0;i<a.length;i++){
if (!m.contains(input[i]))
l.add(input[i]);
}
return l;
}
public class MissingNumber{
static int[] array = { 1, 3, 5 };
public static void getMissingNumber() {
for (int i = 0; i < array.length; i++)
System.out.println(array[i] + " ");
System.out.println("The Missing Number is:");
int j = 0;
for (int i = 1; i <= 5; i++) {
if (j < array.length && i == array[j])
j++;
else
System.out.println(i + " ");
}
}
public static void main(String[] args) {
getMissingNumber();
}
}
i值，使得a[i+1]-a[i] != 1。由于所示算法也必须遍历数组中的所有值，因此在数据有序时，二次方程式没有明显的优势。如果数据不能保证有序，则二次方程式的解需要线性时间（O（N）），而排序的解需要 O（N.log（N））的时间。 - Jonathan Leffler