查找在数组中的丢失和重复的元素以线性时间和恒定空间 [英] Find the missing and duplicate elements in an array in linear time and constant space

问题描述

你给出的 N 64位整数数组。 N可以是非常大的。你知道，每个整数1..N数组中出现一次，但有一个整数失踪，有一个整数复制。

You’re given an array of N 64 bit integers. N may be very large. You know that every integer 1..N appears once in the array, except there is one integer missing and one integer duplicated.

写的线性时间算法来寻找失踪的和重复的数字。此外，你的算法应该在不断的小空间中运行，并保持数组不变。

Write a linear time algorithm to find the missing and duplicated numbers. Further, your algorithm should run in small constant space and leave the array untouched.

来源：<一href="http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/">http://maxschireson.com/2011/04/23/want-a-job-working-on-mongodb-your-first-online-interview-is-in-this-post/

推荐答案

如果所有的数字是present阵列中的金额将是 N（N + 1）/ 2 。

If all numbers were present in the array the sum would be N(N+1)/2.

确定通过总结阵列中的所有号码为O（n）的实际金额，让这成为总和（实际）。

Determine the actual sum by summing up all numbers in the array in O(n), let this be Sum(Actual).

壹号丢失，让这成为Ĵ和一个数字是重复的，让这成为 K 。这意味着，

One number is missing, let this be j and one number is duplicated, let this be k. That means that

总和（实际）= N（N + 1）/ 2 + K - J

Sum(Actual) = N(N+1)/2 + k - j

这是派生

K =萨姆（实际）-N（N + 1）/ 2 + J

k = Sum(Actual) -N(N+1)/2 + j

此外，我们可以计算平方和阵列中，这将总结到 ñ ³ / 3 + N ² / 2 + N / 6，如果所有的数字是present。

Also we can calculate the sum of squares in the array, which would sum up to n³/3 + n²/2 + n/6 if all numbers were present.

现在，我们可以计算出正方形的实际金额为O（N），让这成为总和（实际平方）。

Now we can calculate the actual sum of squares in O(n), let this be Sum(Actual Squares).

总和（实际平方）= N ³ / 3 +   ñ ² / 2 + N / 6 + K ²    - J ²

Sum(Actual Squares) =n³/3 + n²/2 + n/6 + k² - j²

现在我们有两个方程，我们能够确定Ĵ和 K 。

Now we have two equations with which we can determine j and k.

这篇关于查找在数组中的丢失和重复的元素以线性时间和恒定空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！