在具有两个缺失值的整数数组中查找2个缺少的数字

你怎么做到这一点？ 值未排序但是[1..n]示例数组[3,1,2,5,7,8] 。 答案： 4, 6

我在另一篇类似的post中看到了这个解决方案，但我不明白最后一步

 Find the sum of the numbers S=a1+...+an. Also find the sum of squares T=a1*a1+...+an*an. You know that the sum should be S'=1+...+n=n(n+1)/2 You know that the sum of squares should be T'=1^2+...+n^2=n(n+1)(2n+1)/6. Now set up the following system of equations x+y=S'-S, x^2+y^2=T'-T. Solve by writing x^2+y^2=(x+y)^2-2xy => xy=((S'-S)^2-(T'-T))/2. And now the numbers are merely the roots of the quadratic in z: z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0. 

在z为未知的最后一步中设置二次方程的解释是什么？ 解决这个问题背后的直觉是什么？

Answer 1

此方法不可取，因为它遇到integer溢出问题。 所以使用XOR方法找到两个数字，这是非常高效的。 如果你有兴趣我可以解释。

根据@ordinary下面的请求，我正在解释算法：

编辑

假设数组a[]的最大元素是B即假设a[]={1,2,4} ，这里3和5不存在于[]中，因此最大元素是B=5 。

• xor数组a到X所有元素
• xor从1到B到x所有元素
• 通过x = x &(~(x-1));找到x的最左位组x = x &(~(x-1));
• 现在，如果a[i] ^ x == x不是a[i] ^ x == x或a[i]到p ，则q
• 现在对于从1到B所有k ，如果k ^ x == x不是k ^ x == x或p k ^ x == x q
• 现在打印p和q

certificate：

设a = {1,2,4}且B为5，即从1到5，缺失的数字是3和5

一旦我们对a元素和从1到5的数字进行XOR ，我们就得到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所有元素相互比我们将得到的那样5.因此答案。

java中的代码

 public void findNumbers(int[] a, int B){ int x=0; for(int i=0; i 

Answer 2

设x和y是二次方程的根。

• 根的和， SUM = x + y
• 根的PRODUCT ， PRODUCT = x * y

如果我们知道总和和乘积，我们可以将二次方程重建为：

 z^2 - (SUM)z + (PRODUCT) = 0 

在你提到的算法中，我们找到总和和乘积，然后我们用上面的公式重建二次方程。

如果您对详细的推导感兴趣，请参考以下内容 。 阅读“从根的总和和乘积重构二次方程” 。

Answer 3

我有一个针对上述问题的算法。

假设

 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 

现在我们需要找到ab= sqrt[(a+b)^2 -4ab] 。

如果你计算：

 ab= 3 

现在

 a+b=7 ab=3 

添加两个方程式：

 2a=10, a=5 

然后b=7-5=2因此，缺少2和5 。

Answer 4

从…开始

 x+y == SUM xy == PRODUCT 

有两种情况。 如果PRODUCT为零，则一个数字为0 ，另一个数字为SUM 。 否则两者都不为零; 我们可以将第一个等式乘以x而不改变相等性：

 x*x + xy == x*SUM 

替换第二个等式：

 x*x + PRODUCT = x*SUM 

并以通常的forms重新排列

 x*x - x*SUM + PRODUCT = 0 

以便

 x = SUM/2 + sqrt(SUM*SUM - 4*PRODUCT)/2 y = SUM/2 - sqrt(SUM*SUM - 4*PRODUCT)/2 

Answer 5

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 

Answer 6

 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] ab=[3,4] public list find(int[] input){ int[] a= new int[] {1,2,3,4,5};//create a new array without missing numbers List l = new ArrayList();//list for missing numbers Map m = new HashMap(); //populate a hashmap with the elements in the new array for(int i=0;i 

Answer 7

我希望这个程序对你们大家都有用，我把限制到10，它可以用同样的方式完成，只需使用n作为限制并执行相同的操作。

 #include  #include 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"<>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:"<
 

Answer 8

 #include  #include  /* 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); } 

Answer 9

 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(); } 

}

Answer 10

@slider答案的代码示例（ Java ）

  /** * get 2 missed numbers from randomly shuffled array of unique elements from [1,n] * * @param array - shuffled array of unique elements from [1,n], but 2 random elements was missed. len = n-2 * @return array with 2 missed elements */ public static int[] getMissedNumbers(int[] array) { int sum = 0; int fullSum = 0; int fullProduct = 1; int product = 1; for (int i = 0; i < array.length + 2; i++) { int currNaturalNumber = i + 1; fullSum = fullSum + currNaturalNumber; fullProduct = fullProduct * currNaturalNumber; if (i < array.length) { sum = sum + array[i]; product = product * array[i]; } } int missedSum = fullSum - sum; //firstMissedNum + secondMissedNum int missedProduct = fullProduct / product; //firstMissedNum * secondMissedNum //ax*x + bx + c = 0 //x = (-b +- sqrt(b*b - 4*a*c))/2*a // -b = missedSum , c = missedProduct, a = 1 Double firstMissedNum = (missedSum + Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2; Double secondMissedNum = (missedSum - Math.sqrt(missedSum * missedSum - 4 * missedProduct)) / 2; return new int[]{firstMissedNum.intValue(), secondMissedNum.intValue()}; } 

用于测试的简单数组生成器

  public static Map.Entry generateArray(int maxN, int missedNumbersCount) { int[] initialArr = new int[maxN]; for (int i = 0; i < maxN; i++) { initialArr[i] = i + 1; } shuffleArray(initialArr); int[] skippedNumbers = Arrays.copyOfRange(initialArr, maxN - missedNumbersCount, maxN); int[] arrayWithoutSkippedNumbers = Arrays.copyOf(initialArr, maxN - missedNumbersCount); return new AbstractMap.SimpleEntry<>(arrayWithoutSkippedNumbers, skippedNumbers); } private static void shuffleArray(int[] ar) { Random rnd = ThreadLocalRandom.current(); for (int i = ar.length - 1; i > 0; i--) { int index = rnd.nextInt(i + 1); // Simple swap int a = ar[index]; ar[index] = ar[i]; ar[i] = a; } } 

Answer 11

 #include  using namespace std; int main() { int arr[]={3,1,2,5,7,8}; int n=6; for(int i=0;i0 && arr[i]<=n){ int temp=arr[i]-1; if(arr[i]!=arr[temp]){ swap(arr[i],arr[temp]); i--; } } } for(int i=0;i 

我们可以使用相同的数组作为存储桶。 我们遍历它一次并继续将元素交换到正确的索引。 如果该值小于1或大于数组长度，我们保持原样。 初始arrays-3 1 2 5 7 8交换（3,5）5 1 2 3 7 8交换（5,8）8 1 2 3 7 5此后我们再次遍历arrays。 没有处于正确位置的元素缺失，因此我们打印索引。 时间复杂度-O（n）

Answer 12

你只需要对完整数组给出的数组进行异或，找出无零元素….