Il modo più veloce per trovare 2 numeri mancanti in un array

Question

Questa domanda esiste solo per pura curiosità. Non è un compito a casa.

trovare il modo più veloce per trovare due numero mancante in un array 1..n

Così, in un post correlati: Quickest way to find missing number in an array of numbers ho scoperto che si può fare questo abbastanza rapidamente sommando e sottraendo totale.

ma che dire di 2 numeri?

Quindi, le nostre opzioni sono:

1. La ricerca sequenziale
2. Riassumendo articoli, sottraendo dal totale per tutti gli elementi da 1..n, quindi la ricerca tutti i casi possibili.

C'è altro? Possibile avere la soluzione O (n)? Ho trovato questo nella sezione rubino di uno dei siti web, ma qualsiasi lingua è considerata (a meno che non ci siano alcune cose specifiche per una lingua)

Answer 1

Il modo semplice (e abbastanza veloce troppo :)

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

Answer 2

Mi piace l'idea di riassumere e confrontare il risultato con il valore atteso. Quindi la mia idea è di dividere l'array in parti uguali, sommarli e vedere se a entrambi i lati manca un numero. Se una metà è corretta, puoi scorrere l'altra metà (contenente entrambi i numeri mancanti ..... che suona così sbagliato dal punto di vista linguistico>. <) finché non sei riuscito a separare i numeri.

Questo approccio è abbastanza veloce se abs (i-j) è grande - o in parole: quando i numeri mancanti sono abbastanza distanti l'uno dall'altro.

Answer 3

1. Trova la somma dei numeri S=a1+...+an.
2. Trova anche la somma dei quadrati T=a1*a1+...+an*an.
3. Si sa che la somma deve essere S'=1+...+n=n(n+1)/2
4. Si sa che la somma dei quadrati deve essere T'=1^2+...+n^2=n(n+1)(2n+1)/6.
5. Ora impostare il seguente sistema di equazioni x+y=S'-S, x^2+y^2=T'-T.
6. Risolvere scrivendo x^2+y^2=(x+y)^2-2xy =>xy=((S'-S)^2-(T'-T))/2. E ora i numeri sono semplicemente le radici del quadratic in z: z^2-(S'-S)z+((S'-S)^2-(T'-T))/2=0.

Answer 4

Creare un insieme dei numeri da 1 a N. Calcolare la differenza di questo insieme con l'insieme di numeri dalla matrice. Poiché i numeri sono distinti, il risultato saranno i numeri mancanti. O(N) tempo e spazio.

Answer 5

ho ottenuto il miglior tempo tra i miei test con il seguente approccio (un po 'più veloce che con la sostituzione di 2 array):

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

Che cosa succede se non sapevi quali sono stati i numeri della matrice ?Se tu fossi appena dato un array e detto che c'era un numero mancante, ma non ha avuto alcuna conoscenza di ciò che i numeri erano in là si potrebbe usare questo:

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

Supponiamo array per essere [1,4, 2,3,7]. I numeri mancanti sono 5,6

Passaggio 1: aggiungere tutti i numeri nell'array. 17. Sappiamo la somma di 1..7 (n * (n + 1)/2) = 28.

Così x + y + 17 = 28 => x + y = 11

Fase 2 : Moltiplica tutti i numeri nell'array. 168. Sappiamo il prodotto di 1..7 = 5040.

Quindi 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 

Abbiamo x + y = 11 e xy = 1. Risolvi per x, y.

Questa soluzione non richiede spazio di memoria aggiuntivo e viene eseguita in 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); 
    } 
} 

---

uscita:

ab=2 

sub_of_ab=1 

sum_of_ab=3 

Missing number is 1 and 2 

Answer 9

propongo la seguente soluzione

metodo di bisezione sulla #Swift trovare 2 numeri mancanti in matrice

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. 

}