在一个数组中找到两个缺失数字的最快方法

Question

这个问题存在只是因为好奇心，不是作业。

寻找在1..n范围内数组中丢失的两个数字的最快方法。

所以，在相关的帖子中：在一个数字数组中查找缺失数字的最快方法 我发现你可以通过求和并减去总数来很快地完成这个任务。

但是对于两个数字呢？

因此，我们的选择是：

1. 顺序搜索
2. 先将所有项求和，然后从1...n的全部元素总和中减去该和，再搜索所有可能情况。

还有别的吗？ 有可能有O(n)的解决方案吗？ 我在某个网站的ruby部分发现了这个问题，但任何语言都可以考虑（除非某些语言有特定的问题）。

- user194076

---

你可以简单地对数组进行排序，这可以在O(n log n)的时间内完成。之后，您可以循环遍历已排序的数据，并检测数字i是否没有被n+1跟随。这将增加另一个n，但仍将保持在O(n log n)的时间复杂度内。 - Martin Thurau

你的问题不够清楚。你说的数组1..n缺少什么数字呢（可能是指(1..n).to_a）？难道它不包含所有数吗？如果链接中有一些细节，它还是无法帮助我们的。你需要在这里清楚地陈述问题。 - sawa

“Fastest”是一个不明确的概念。最快的算法和可能最快的Ruby实现，重复的内容：https://dev59.com/dXA75IYBdhLWcg3wDUq2。最好的Ruby高手：可能是steenslag的答案。 - Ciro Santilli OurBigBook.com

Answer 1

1. 找出数列的和 S=a1+...+an。
2. 同时找出平方和 T=a1*a1+...+an*an。
3. 已知总和应为 S'=1+...+n=n(n+1)/2
4. 已知平方和应为 T'=1^2+...+n^2=n(n+1)(2n+1)/6。
5. 现在建立以下方程组 x+y=S'-S, x^2+y^2=T'-T。
6. 通过写出 x^2+y^2=(x+y)^2-2xy => xy=((S'-S)^2-(T'-T))/2 来解决。现在这些数字仅是二次方程中的根 z：z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0。

- Peteris

---

我不理解最后一步的最后一部分。你怎么知道要设置那个二次方程？ - ordinary

问题开放以解释最后一步骤：https://dev59.com/eGIj5IYBdhLWcg3wpmsH?lq=1 - Ciro Santilli OurBigBook.com

Answer 2

简单且相当快速的方法 :)

a = [1,2,3,5,7]
b = (1..7).to_a
p b-a #=> [4, 6]

- steenslag

---

@aMichael J. Barber，这个操作不需要对数组a进行排序即可生效。 - steenslag

由于该算法具有二次复杂度，因此它并不是“相当快速”的，而已知存在一种相当简单的线性解决方案（请参见下面的答案）。 - Jakub Arnold

Answer 3

假设数组为 [1,4,2,3,7]。缺失的数字是 5 和 6。

步骤1：将数组中的所有数字相加。结果为17。我们知道1..7这个数列的总和是28（n*(n+1)/2）。因此，x+y+17=28 => x+y=11。

步骤2：将数组中的所有数字相乘。结果为168。我们知道1..7这个数列的乘积为5040。因此，x*y*168 = 5040 => x*y=30。

(x+y)^2 = x^2 + 2xy + y^2 
=> 121 = 60 + x^2 + y^2
=> x^2 + y^2 = 61

(x-y)^2 = x^2 - 2xy + y^2 
=> (x-y)^2 = 61 - 60
=> (x-y)^2 = 1 
=> x-y = 1

我们有x+y=11和x-y=1。求解x，y。

这个解决方案不需要额外的内存空间，并且可以在O(n)时间内完成。

- fragzilla

---

我喜欢这个解决方案！+1 - Abdo

乘法的结果可以轻松超过Integer.MAX_VALUE。 - Meow

这非常容易理解。 - sysuser

Answer 4

我在测试中采用了以下方法，取得了最快的时间（比使用2个数组替换略快）：

n = 10
input = [3, 6, 8, 2, 1, 9, 5, 7]

temp = Array.new(n+1, 0)
input.each { |item| temp[item] = 1 }
result = []
1.upto(n) { |i| result << i if temp[i] == 0 }

- Aliaksei Kliuchnikau

Answer 5

创建一个由1到N的数字集合。计算该集合与数组中数字集合的差异。由于这些数字是不同的，结果将是缺失的数字。O(N)时间和空间复杂度。

- Michael J. Barber

---

无论实现方式如何，创建集合或计算差异都比O(N)慢。 - Karoly Horvath

@yi_H 使用哈希表。或者，由于它是有限集合，可以使用长度为N的数组。这两种方法的时间复杂度均为O(N)。 - Michael J. Barber

Answer 6

If the array is sorted from 0 to N then you can compare the difference with index. The recursion function for this is O(logN)
Pseudo code for it is: 
// OffsetA will keep track of the index offset of our first missing Number
// OffsetB will keep track of our second missing number
// Both Offset are set to Zero on the first recursion call. 

Missing( Array A , Array B , OffsetA,  OffsetB ){
Add Array's A and B together. Will call it array C.// At the beginning Array B would be empty.

BaseCase:  If array C.length is 2 return C

    M= C.length/2 

// for the middle value.

    If (C[M] == M + OffsetA){ // This means that both the values that are missing are to the right side of the array.
       return Missing((Arrays.copyOfRange(C,M,C.length)),ArrayB,M + Of

    fsetA,OffsetB);
    }

    If (C[M] == M + OffsetA +2){// This means both our values are to the left side of the missing array

     return Missing((Arrays.copyOfRange(C,0,M)),ArrayB,OffsetA,OffsetB);
    }

//This is the more complicated one.

`If(C[M] == M + OffsetA + 1){` This means that their are values on both the left and right side of the array. So we have to check the the middle of the first half and the middle of the second half of the array and we send the two quarter parts into our Missing Function. The checks are pretty much the same as the if statements up top but you should be able to figure out them your self. It seems like a homework or interview question. 



EDIT: There might me a small issue with the offset switching and I dont have time to change it now but you should be able to figure out the basic concept. 

}

- Grisha Kamyshnikov

Answer 7

如果你不知道数组中的数字是什么怎么办？如果你只是被给定一个数组，并告诉有一个数字缺失，但你没有任何关于这些数字的知识，你可以使用以下方法：

array = array.uniq.sort!  # Just to make sure there are no dupes and it's sorted.
i = 0
while i < n.length-1
  puts n[i] + 1 if n[i] + 1 != n[i+1]
  i+=1
end

- mjd2

---

这是否假设数字是从1到length-1？否则，谁能说不是缺少了-10呢？ - Teepeemm

Answer 8

public class TwoNumberMissing {
    int fact(int x) {
        if (x != 0)
            return x * fact(x - 1);
        else
            return 1;
    }

    public static void main(String[] args) {
        TwoNumberMissing obj = new TwoNumberMissing();
        int a[] = { 1, 2, 3, 4, 5 };
        int sum = 0;
        int sum_of_ab = 0;
        for (int i = 0; i < a.length; i++) {
            sum = sum + a[i];
        }
        int b[] = {4,5,3};
        int prod = 1;
        int sum1 = 0;
        for (int i = 0; i < b.length; i++) {
            prod = prod * b[i];
            sum1 = sum1 + b[i];
        }
        int ab = obj.fact(a.length) / prod;
        System.out.println("ab=" + ab);
        sum_of_ab = sum - sum1;
        int sub_of_ab = (int) (Math.sqrt(sum_of_ab * sum_of_ab - 4 * ab));
        System.out.println("sub_of_ab=" + sub_of_ab);
        System.out.println("sum_of_ab=" + sum_of_ab);
        int num1=(sum_of_ab+sub_of_ab)/2;
         int num2=(int)ab/num1;
         System.out.println("Missing number is "+num2+" and "+num1);
    }
}

---

输出：

ab=2

sub_of_ab=1

sum_of_ab=3

Missing number is 1 and 2

- Aman Kumar

Answer 9

我提出以下解决方案：

在 #Swift 上使用二分法，在数组中找到 2 个缺失的数字。

private func find(array: [Int], offset: Int, maximal: Int, missing: Int) -> [Int] {

    if array.count <= missing + 1 {
        var found = [Int]()
        var valid = offset + 1

        for value in array {
            if value != valid + found.count {
                found.append(valid)
            }
            valid += 1
        }
        return found
    }

    let maxIndex: Int = array.count
    let maxValue: Int = maximal - offset

    let midIndex: Int = maxIndex / 2
    let midValue: Int = array[midIndex - 1] - offset

    let lostInFirst: Int = midValue - midIndex
    let lostInSecond: Int = maxValue - maxIndex - lostInFirst

    var part1 = [Int]()
    var part2 = [Int]()

    if lostInFirst > 0 {
        let subarray = Array(array[0..<midIndex])
        part1 = find(array: subarray, offset: offset, maximal: midIndex + offset + lostInFirst + 1, missing: lostInFirst)
    }

    if lostInSecond > 0 {
        let subarray = Array(array[midIndex..<maxIndex])
        part2 = find(array: subarray, offset: midIndex + offset + lostInFirst, maximal: maximal, missing: lostInSecond)
    }

    return part1 + part2
}

- Sergey Sergeyev

Answer 10

我喜欢将结果相加并与期望值进行比较的想法。因此，我的想法是将数组分成相等的部分，将它们相加，并查看两侧是否缺少一个数字。如果一半正确，您可以迭代另一半（包含两个缺失数字...从语言角度来看，这听起来很奇怪>.<），直到您成功分离数字。

如果abs(i-j)很大，这种方法非常快-或者换句话说：当缺失的数字相距很远时。

- nuala