Erhalte einen O (N) -Algorithmus, um ein Produkt aus einer Sammlung von Zahlen mit einer seltsamen Einschränkung zu finden

8

Dies ist eine Frage, als ich an einem kürzlichen Interview teilgenommen habe, ich denke es ist interessant. Nehmen wir an: int n = 10;

Eingabe: Ein Array int a[10];

Ausgabe: Ein Array float b[10];

Voraussetzung:

%Vor%

Problem: Wie können wir das Array b bevölkert ohne den Divisionsoperator / erhalten? Und mit einem O(n) -Algorithmus?

Ich habe einige Methoden ausprobiert, aber immer noch vergeblich. Irgendwelche Ideen?

    
David 09.05.2013, 16:16
quelle

2 Antworten

15

Berechnen Sie zunächst alle linken und rechten Produkte:

%Vor%

Beachten Sie, dass left[i] == left[i-1] * a[i] , also das left -Array in linearer Zeit berechnet werden kann. Gleichermaßen kann das right -Array in linearer Zeit berechnet werden.

Von left und right kann das Array b in linearer Zeit von b[i] = left[i-1] * right[i+1] mit Sonderfällen für i == 0 und i == n berechnet werden.

    
Egor Skriptunoff 09.05.2013, 16:28
quelle
1

Nach der Idee von Egor Skriptunoff habe ich diesen Code geschrieben: Es ist einfacher zu verstehen:

%Vor%     
Gisway 09.05.2013 18:35
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset jQuery-Fehler TypeError: $ .event.handle ist nicht definiert