Geben Sie bei einem Array von Zahlen ein Array von Produkten aller anderen Nummern zurück (keine Unterteilung).

Diese Frage wurde mir in einem Vorstellungsgespräch gestellt und ich würde gerne wissen, wie andere sie lösen würden. Ich bin mit Java am besten vertraut, aber Lösungen in anderen Sprachen sind willkommen.

Geben Sie bei einem Array von Zahlen numsein Array von Zahlen zurück products, wobei products[i]das Produkt von allen ist nums[j], j != i.

Input : [1, 2, 3, 4, 5]
Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)]
      = [120, 60, 40, 30, 24]

Sie müssen dies O(N)ohne Division tun .

Eine Erklärung der Polygenelubricants- Methode lautet: Der Trick besteht darin, die Arrays zu konstruieren (im Fall für 4 Elemente).

{              1,         a[0],    a[0]*a[1],    a[0]*a[1]*a[2],  }
{ a[1]*a[2]*a[3],    a[2]*a[3],         a[3],                 1,  }

Beides kann in O (n) erfolgen, indem am linken bzw. rechten Rand begonnen wird.

Wenn Sie dann die beiden Arrays Element für Element multiplizieren, erhalten Sie das gewünschte Ergebnis

Mein Code würde ungefähr so ​​aussehen:

int a[N] // This is the input
int products_below[N];
p=1;
for(int i=0;i<N;++i) {
  products_below[i]=p;
  p*=a[i];
}

int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
  products_above[i]=p;
  p*=a[i];
}

int products[N]; // This is the result
for(int i=0;i<N;++i) {
  products[i]=products_below[i]*products_above[i];
}

Wenn Sie auch im Weltraum O (1) sein müssen, können Sie dies tun (was meiner Meinung nach weniger klar ist).

int a[N] // This is the input
int products[N];

// Get the products below the current index
p=1;
for(int i=0;i<N;++i) {
  products[i]=p;
  p*=a[i];
}

// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
  products[i]*=p;
  p*=a[i];
}

Hier ist eine kleine rekursive Funktion (in C ++), um die Modifikation an Ort und Stelle durchzuführen. Es erfordert jedoch O (n) zusätzlichen Speicherplatz (auf dem Stapel). Angenommen, das Array befindet sich in a und N enthält die Array-Länge, die wir haben

int multiply(int *a, int fwdProduct, int indx) {
    int revProduct = 1;
    if (indx < N) {
       revProduct = multiply(a, fwdProduct*a[indx], indx+1);
       int cur = a[indx];
       a[indx] = fwdProduct * revProduct;
       revProduct *= cur;
    }
    return revProduct;
}

Hier ist mein Versuch, es in Java zu lösen. Entschuldigung für die nicht standardmäßige Formatierung, aber der Code weist viele Duplikate auf, und dies ist das Beste, was ich tun kann, um ihn lesbar zu machen.

import java.util.Arrays;

public class Products {
    static int[] products(int... nums) {
        final int N = nums.length;
        int[] prods = new int[N];
        Arrays.fill(prods, 1);
        for (int
           i = 0, pi = 1    ,  j = N-1, pj = 1  ;
           (i < N)         && (j >= 0)          ;
           pi *= nums[i++]  ,  pj *= nums[j--]  )
        {
           prods[i] *= pi   ;  prods[j] *= pj   ;
        }
        return prods;
    }
    public static void main(String[] args) {
        System.out.println(
            Arrays.toString(products(1, 2, 3, 4, 5))
        ); // prints "[120, 60, 40, 30, 24]"
    }
}

Die Schleifeninvarianten sind pi = nums[0] * nums[1] *.. nums[i-1]und pj = nums[N-1] * nums[N-2] *.. nums[j+1]. Der ilinke Teil ist die "Präfix" -Logik, und jder rechte Teil ist die "Suffix" -Logik.

Rekursiver Einzeiler

Jasmeet gab eine (schöne!) Rekursive Lösung; Ich habe daraus diesen (abscheulichen!) Java-Einzeiler gemacht. Es werden Änderungen an Ort und Stelle mit O(N)temporärem Speicherplatz im Stapel vorgenommen.

static int multiply(int[] nums, int p, int n) {
    return (n == nums.length) ? 1
      : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
          + 0*(nums[n] *= p);
}

int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"

Michael Andersons Lösung in Haskell übersetzen:

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

Schleichende Umgehung der Regel "keine Teilung":

sum = 0.0
for i in range(a):
  sum += log(a[i])

for i in range(a):
  output[i] = exp(sum - log(a[i]))

Los geht's, einfache und saubere Lösung mit O (N) -Komplexität:

int[] a = {1,2,3,4,5};
    int[] r = new int[a.length];
    int x = 1;
    r[0] = 1;
    for (int i=1;i<a.length;i++){
        r[i]=r[i-1]*a[i-1];
    }
    for (int i=a.length-1;i>0;i--){
        x=x*a[i];
        r[i-1]=x*r[i-1];
    }
    for (int i=0;i<r.length;i++){
        System.out.println(r[i]);
    }

C ++, O (n):

long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
          bind1st(divides<long long>(), prod));

1. Reisen Sie nach links-> rechts und speichern Sie das Produkt weiter. Nennen wir es Vergangenheit. -> O (n)
2. Reisen Sie nach rechts -> nach links und bewahren Sie das Produkt auf. Nennen wir es Zukunft. -> O (n)
3. Ergebnis [i] = Vergangenheit [i-1] * Zukunft [i + 1] -> O (n)
4. Vergangenheit [-1] = 1; und Zukunft [n + 1] = 1;

Auf)

Hier ist meine Lösung in modernem C ++. Es macht Gebrauch std::transformund ist ziemlich leicht zu merken.

Online-Code (Zauberstabbox).

#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

vector<int>& multiply_up(vector<int>& v){
    v.insert(v.begin(),1);
    transform(v.begin()+1, v.end()
             ,v.begin()
             ,v.begin()+1
             ,[](auto const& a, auto const& b) { return b*a; }
             );
    v.pop_back();
    return v;
}

int main() {
    vector<int> v = {1,2,3,4,5};
    auto vr = v;

    reverse(vr.begin(),vr.end());
    multiply_up(v);
    multiply_up(vr);
    reverse(vr.begin(),vr.end());

    transform(v.begin(),v.end()
             ,vr.begin()
             ,v.begin()
             ,[](auto const& a, auto const& b) { return b*a; }
             );

    for(auto& i: v) cout << i << " "; 
}

Dies ist O (n ^ 2), aber f # ist soooo schön:

List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed) 
          [1;1;1;1;1]
          [1..5]

Berechnen Sie das Produkt der Zahlen links und rechts von jedem Element vor. Für jedes Element ist der gewünschte Wert das Produkt der Produkte seiner Nachbarn.

#include <stdio.h>

unsigned array[5] = { 1,2,3,4,5};

int main(void)
{
unsigned idx;

unsigned left[5]
        , right[5];
left[0] = 1;
right[4] = 1;

        /* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
        left[idx] = left[idx-1] * array[idx-1];
        }

        /* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
        right[idx] = right[idx+1] * array[idx+1];
        }

for (idx=0; idx <5 ; idx++) {
        printf("[%u] Product(%u*%u) = %u\n"
                , idx, left[idx] , right[idx]  , left[idx] * right[idx]  );
        }

return 0;
}

Ergebnis:

$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24

(UPDATE: Jetzt schaue ich genauer hin, dies verwendet die gleiche Methode wie Michael Anderson, Daniel Migowski und Polygenelubricants oben)

Tricky:

Verwenden Sie Folgendes:

public int[] calc(int[] params) {

int[] left = new int[n-1]
in[] right = new int[n-1]

int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
    fac1 = fac1 * params[i];
    fac2 = fac2 * params[n-i];
    left[i] = fac1;
    right[i] = fac2; 
}
fac = 1;

int[] results = new int[n];
for( int i=0; i<n; i++ ) {
    results[i] = left[i] * right[i];
}

Ja, ich bin sicher, ich habe einige i-1 anstelle von i verpasst, aber das ist der Weg, um es zu lösen.

Es gibt auch eine nicht optimale O (N ^ (3/2)) - Lösung. Es ist jedoch ziemlich interessant.

Verarbeiten Sie zuerst jede Teilmultiplikation der Größe N ^ 0,5 vor (dies erfolgt in O (N) -Zeitkomplexität). Dann kann die Berechnung für das Vielfache der anderen Werte jeder Zahl in 2 * O (N ^ 0,5) durchgeführt werden (warum? Weil Sie nur die letzten Elemente anderer ((N ^ 0,5) - 1) Zahlen multiplizieren müssen. und multiplizieren Sie das Ergebnis mit ((N ^ 0,5) - 1) Zahlen, die zur Gruppe der aktuellen Zahl gehören). Wenn man dies für jede Zahl tut, kann man O (N ^ (3/2)) Zeit bekommen.

Beispiel:

4 6 7 2 3 1 9 5 8

Teilergebnisse: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

Um den Wert 3 zu berechnen, muss man die Werte 168 * 360 der anderen Gruppen multiplizieren und dann mit 2 * 1.

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5 };
    int[] result = { 1, 1, 1, 1, 1 };
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
            result[i] *= arr[j];

        }
        for (int k = arr.length - 1; k > i; k--) {
            result[i] *= arr[k];
        }
    }
    for (int i : result) {
        System.out.println(i);
    }
}

Diese Lösung habe ich mir ausgedacht und fand es so klar, was denkst du?

def productify(arr, prod, i):
    if i < len(arr):
            prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
            retval = productify(arr, prod, i + 1)
            prod[i] *= retval
            return retval * arr[i]
    return 1

arr = [1, 2, 3, 4, 5] prod = [] produktiviere (arr, prod, 0) drucke prod

Um hier vollständig zu sein, ist der Code in Scala:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

Dadurch wird Folgendes ausgedruckt:

120
60
40
30
24

Das Programm filtert das aktuelle Element heraus (_! = Element); und multiplizieren Sie die neue Liste mit der Methode reduLeft. Ich denke, dies ist O (n), wenn Sie Scala View oder Iterator für Lazy Eval verwenden.

Basierend auf der Antwort von Billz - Entschuldigung, ich kann keinen Kommentar abgeben, aber hier ist eine Scala-Version, die doppelte Elemente in der Liste korrekt behandelt und wahrscheinlich O (n) ist:

val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force

kehrt zurück:

List(1008, 144, 336, 336, 252, 252)

Ich habe hier meine Javascript-Lösung hinzugefügt, da ich niemanden gefunden habe, der dies vorschlägt. Was ist zu teilen, außer zu zählen, wie oft Sie eine Zahl aus einer anderen Zahl extrahieren können? Ich habe das Produkt des gesamten Arrays berechnet, dann über jedes Element iteriert und das aktuelle Element bis Null subtrahiert:

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
  var res = [];
  var totalProduct = 1;
  //calculate the total product
  for(var i = 0; i < input.length; i++){
    totalProduct = totalProduct * input[i];
  }
  //populate the result array by "dividing" each value
  for(var i = 0; i < input.length; i++){
    var timesSubstracted = 0;
    var divisor = input[i];
    var dividend = totalProduct;
    while(divisor <= dividend){
      dividend = dividend - divisor;
      timesSubstracted++;
    }
    res.push(timesSubstracted);
  }
  return res;
}

Ich bin an C # gewöhnt:

    public int[] ProductExceptSelf(int[] nums)
    {
        int[] returnArray = new int[nums.Length];
        List<int> auxList = new List<int>();
        int multTotal = 0;

        // If no zeros are contained in the array you only have to calculate it once
        if(!nums.Contains(0))
        {
            multTotal = nums.ToList().Aggregate((a, b) => a * b);

            for (int i = 0; i < nums.Length; i++)
            {
                returnArray[i] = multTotal / nums[i];
            }
        }
        else
        {
            for (int i = 0; i < nums.Length; i++)
            {
                auxList = nums.ToList();
                auxList.RemoveAt(i);
                if (!auxList.Contains(0))
                {
                    returnArray[i] = auxList.Aggregate((a, b) => a * b);
                }
                else
                {
                    returnArray[i] = 0;
                }
            }
        }            

        return returnArray;
    }

Wir können zuerst das nums[j](Wo j != i) von der Liste ausschließen und dann das Produkt des Restes erhalten; Das Folgende ist ein python way, um dieses Rätsel zu lösen:

from functools import reduce
def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print(products([1, 2, 3, 4, 5]))

[out]
[120, 60, 40, 30, 24]

Nun, diese Lösung kann als die von C / C ++ angesehen werden. Nehmen wir an, wir haben ein Array "a", das n Elemente wie a [n] enthält, dann wäre der Pseudocode wie folgt.

for(j=0;j<n;j++)
  { 
    prod[j]=1;

    for (i=0;i<n;i++)
    {   
        if(i==j)
        continue;  
        else
        prod[j]=prod[j]*a[i];
  }

Eine weitere Lösung: Division verwenden. mit zweimaliger Durchquerung. Multiplizieren Sie alle Elemente und teilen Sie sie durch jedes Element.

{-
Rekursive Lösung mit sqrt (n) -Untergruppen. Läuft in O (n).

Berechnet rekursiv die Lösung für sqrt (n) -Untermengen der Größe sqrt (n). 
Dann wird die Produktsumme jeder Teilmenge wiederholt.
Dann berechnet es für jedes Element in jeder Teilmenge das Produkt mit
die Produktsumme aller anderen Produkte.
Dann werden alle Teilmengen abgeflacht.

Die Wiederholung zur Laufzeit ist T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n

Angenommen, T (n) ≤ cn in O (n).

T (n) = sqrt (n) · T (sqrt (n)) + T (sqrt (n)) + n
    ≤ sqrt (n) * c * sqrt (n) + c * sqrt (n) + n
    ≤ c * n + c * sqrt (n) + n
    ≤ (2c + 1) * n
    ∈ O (n)

Beachten Sie, dass die Obergrenze (sqrt (n)) mithilfe einer binären Suche berechnet werden kann 
und O (logn) -Iterationen, wenn der Befehl sqrt nicht zulässig ist.
-}

otherProducts [] = []
otherProducts [x] = [1]
otherProducts [x, y] = [y, x]
otherProducts a = foldl '(++) [] $ zipWith (\ sp -> map (* p) s) gelöste Teilmengen subsetOtherProducts
    wo 
      n = Länge a

      - Teilmengengröße. Benötigen Sie, dass 1 <s <n.
      s = Decke $ sqrt $ fromIntegral n

      gelöste Teilmengen = andere Teilmengen von Produkten zuordnen
      subsetOtherProducts = otherProducts $ map-Produktteilmengen

      Teilmengen = $ loop umkehren a []
          wobei loop [] acc = acc
                Schleife a acc = Schleife (drop sa) ((take sa): acc)

Hier ist mein Code:

int multiply(int a[],int n,int nextproduct,int i)
{
    int prevproduct=1;
    if(i>=n)
        return prevproduct;
    prevproduct=multiply(a,n,nextproduct*a[i],i+1);
    printf(" i=%d > %d\n",i,prevproduct*nextproduct);
    return prevproduct*a[i];
}

int main()
{
    int a[]={2,4,1,3,5};
    multiply(a,5,1,0);
    return 0;
}

Hier ist ein leicht funktionierendes Beispiel mit C #:

            Func<long>[] backwards = new Func<long>[input.Length];
            Func<long>[] forwards = new Func<long>[input.Length];

            for (int i = 0; i < input.Length; ++i)
            {
                var localIndex = i;
                backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
                forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
            }

            var output = new long[input.Length];
            for (int i = 0; i < input.Length; ++i)
            {
                if (0 == i)
                {
                    output[i] = forwards[i + 1]();
                }
                else if (input.Length - 1 == i)
                {
                    output[i] = backwards[i - 1]();
                }
                else
                {
                    output[i] = forwards[i + 1]() * backwards[i - 1]();
                }
            }

Ich bin mir nicht ganz sicher, ob dies O (n) ist, da die erstellten Funcs halb rekursiv sind, aber meine Tests scheinen darauf hinzudeuten, dass es zeitlich O (n) ist.

// Dies ist die rekursive Lösung in Java. // Wird vom Hauptprodukt wie folgt aufgerufen (a, 1,0);

public static double product(double[] a, double fwdprod, int index){
    double revprod = 1;
    if (index < a.length){
        revprod = product2(a, fwdprod*a[index], index+1);
        double cur = a[index];
        a[index] = fwdprod * revprod;
        revprod *= cur;
    }
    return revprod;
}

Eine saubere Lösung mit O (n) Laufzeit:

1. Berechnen Sie für jedes Element das Produkt aller zuvor vorkommenden Elemente und speichern Sie es in einem Array "pre".
2. Berechnen Sie für jedes Element das Produkt aller Elemente, die nach diesem Element auftreten, und speichern Sie es in einem Array "post".

3. Erstellen Sie ein endgültiges Array "Ergebnis" für ein Element i,

   result[i] = pre[i-1]*post[i+1];
   

function solution($array)
{
    $result = [];
    foreach($array as $key => $value){
        $copyOfOriginalArray = $array;
        unset($copyOfOriginalArray[$key]);
        $result[$key] = multiplyAllElemets($copyOfOriginalArray);
    }
    return $result;
}

/**
 * multiplies all elements of array
 * @param $array
 * @return int
 */
function multiplyAllElemets($array){
    $result = 1;
    foreach($array as $element){
        $result *= $element;
    }
    return $result;
}

$array = [1, 9, 2, 7];

print_r(solution($array));

Hier ist ein weiteres einfaches Konzept, das das Problem löst O(N).

        int[] arr = new int[] {1, 2, 3, 4, 5};
        int[] outArray = new int[arr.length]; 
        for(int i=0;i<arr.length;i++){
            int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
            outArray[i] = res/arr[i];
        }
        System.out.println(Arrays.toString(outArray));

Ich habe eine Lösung mit O(n)räumlicher und O(n^2)zeitlicher Komplexität, die unten angegeben ist.

public static int[] findEachElementAsProduct1(final int[] arr) {

        int len = arr.length;

//        int[] product = new int[len];
//        Arrays.fill(product, 1);

        int[] product = IntStream.generate(() -> 1).limit(len).toArray();


        for (int i = 0; i < len; i++) {

            for (int j = 0; j < len; j++) {

                if (i == j) {
                    continue;
                }

                product[i] *= arr[j];
            }
        }

        return product;
    }