Самый быстрый способ найти 2 недостающих числа в массиве

Question

Этот вопрос существует только из-за чистого любопытства. Не домашнее задание.

Найти самый быстрый способ найти два недостающее число в массиве 1..n

Так, в родственном сообщение: Quickest way to find missing number in an array of numbers я узнал, что вы можете сделать это довольно быстро путем суммирования и вычитания суммы.

, но как насчет 2 чисел?

Таким образом, наши варианты:

1. Последовательный поиск
2. Суммируя элементы, вычитая из общей для всех элементов из 1..N, а затем искать все возможные случаи.

Что-нибудь еще? Возможно ли иметь решение O (n)? Я нашел это в рубиновом разделе одного из сайтов, но считается, что на каком-либо языке (если нет каких-либо конкретных вещей для языка)

Answer 1

Простой способ (и довольно быстро тоже :)

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

Answer 2

Мне нравится идея суммирования и сравнения результата с ожидаемым значением. Поэтому моя идея состоит в том, чтобы разделить массив на равные части, суммировать их и посмотреть, нет ли у обеих сторон номера. Если одна половина верна, вы можете перебирать другую половину (содержащую оба недостающих номера ..... это звучит так неправильно с лингвистической точки зрения> <), пока вам не удастся отделить числа.

Этот подход довольно быстр, если abs (i-j) большой - или на словах: когда недостающие числа находятся довольно далеко друг от друга.

Answer 3

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.

Answer 4

Создание набора чисел от 1 до N. Вычислить разность этого множества с множеством чисел из массива. Поскольку числа отличаются друг от друга, результатом будут недостающие числа. O(N) время и пространство.

Answer 5

я получил лучшее время среди моих тестов со следующим подходом (чуть-чуть быстрее, чем с заменой 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 } 

Answer 6

Что делать, если вы не знали, что числа в массиве были ?Если вы только что массив и сказал там был номер отсутствует, но у вас не было каких-либо знаний о том, что номера были там вы могли бы использовать это:

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 

Answer 7

Пусть массив будет [1,4, 2,3,7]. Недостающие числа: 5,6

Шаг 1: добавьте все числа в массив. 17. Мы знаем сумму 1..7 (N * (N + 1)/2) = 28.

Таким образом, х + у + 17 = 28 => х + у = 11

Шаг 2 : Умножьте все числа в массиве. 168. Мы знаем продукт 1..7 = 5040.

Таким образом, х * у * 168 = 5040 => х * у = 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 

Мы имеем х + у = 11 и х = 1. Решите для x, y.

Это решение не требует дополнительного объема памяти и выполняется в O (n).

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 

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 
} 

Answer 10

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. 

}