Array durch Hinzufügen von Elementen reduzieren

Question

Ich bin in einem Test auf diese Frage gestoßen.

Bei einem Array reduzieren Sie das Array auf ein einzelnes Element mit minimalen Kosten. Zum Reduzieren entfernen Sie zwei Elemente aus dem Array, fügen Sie diese beiden Zahlen hinzu und behalten Sie die Summe im Array bei. Die Kosten jeder Operation sind die Summe der in diesem Schritt entfernten Elemente.

Beispiel, lassen Sie das Array A = [1,2,3]

Dann wir 1 und 2 entfernen können, fügen Sie beide und halten Sie die Summe zurück in Array. Kosten dieses Schrittes wären (1 + 2) = 3.

also A = [3,3], Cost = 3

Im zweiten Schritt kann man beiden Elemente aus der Matrix entfernen und halten, die Summe wieder im Array. Kosten für diesen Schritt würde also Gesamtkosten erweist sich als 9 (6 + 3) 3 + 3 = 6.

So, A = [6], Kosten = 6

sein.

Ich habe versucht, das Array zu sortieren, und die Elemente von abnehmender zu steigender, aber es schlägt fehl, wenn es doppelte Elemente gibt.

Pseudo-Code meines Algorithmus

sort(Array) 
cost = 0 
for(i=0; i<Array.length - 1; i++) { 
    Array[i+1] = Array[i] + Array[i+1] 
    cost = cost + Array[i+1] 
} 

Der Algorithmus, der oben erwähnt wurde, funktioniert nicht. Ich habe einen möglichen Fall gefunden, in dem es scheitern könnte. Wenn das Array = [5, 5, 5, 5], dann ist Cost = 45, gemäß dem obigen Algorithmus.

Wenn wir jedoch die ersten zwei Elemente und die letzten zwei Elemente summieren und dann die restlichen zwei Elemente summieren, ergibt sich die Gesamtkosten 40. (Im ersten Schritt Kosten = 10 * 2 und im nächsten Schritt weitere 20)

Was könnte ein effizienter Algorithmus dafür sein?

Answer 1

Sie waren auf dem richtigen Weg, indem Sie das Array sortieren und zuerst die untersten Elemente summieren. Das Problem ist: Die Summe der beiden untersten Elemente könnte größer sein als das nächste Element nach diesen, so dass Sie es nicht einfach in den Vordergrund stellen können. Es kann aber auch kleiner sein als das letzte Element, so dass Sie es auch nicht in den Hintergrund stellen können. Sie müssen die Summe genau an den Ort legen, an dem sie gehört. die Sortierung.

Beispiel: Wenn Ihre Liste [1, 1, 3, 3] ist, 1+1 sollte dann in der Front setzen, dh [2, 3, 3], aber wenn wir [2, 2, 3, 3] haben, dann ist die Summe 2+2 hat in den Rücken [3, 3, 4] und für [2, 2, 3, 5] ist gesetzt werden muss sein in die mittlere Position bringen, dh [3, 4, 5].

Ein einfacher Weg, dies zu tun, ist eine heap Struktur. Diese sind in den meisten Sprachen verfügbar und bieten Methoden zum Abrufen und Entfernen des kleinsten Elements und zum Einfügen eines Elements an der richtigen Stelle. Hier ist ein Beispiel in Python:

import heapq 
def reduce_sum(lst): 
    heapq.heapify(lst) 
    s = 0 
    while len(lst) > 1: 
     first = heapq.heappop(lst) 
     second = heapq.heappop(lst) 
     s += first + second 
     heapq.heappush(lst, first + second) 
    return s 

reduce_sum([1,2,3])  # 9 
reduce_sum([5, 5, 5, 5]) # 40 

Und wenn Sie nicht Heaps verwenden können, können Sie immer noch das Array iterieren den richtigen Platz zu finden, das summierte Element zu setzen, oder binäre Suche verwenden, um so schneller zu tun.

Answer 2

Sie Array wird immer reduziert auf die sum aller seiner Elemente. Die "cost "dieser Reduktion kann jedoch variieren. Die Mindest "cost" durch Hinzufügen von zwei minimalen Elemente erreicht werden könnte, die derzeit in dem Array vorhanden sind.

Min Heap dieses Problem verwendet werden kann, sehr effizient zu lösen. Hier ist ein Beispiel ist in Java .

public int[] sumAndCost(Integer[] arr) { 
     PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Arrays.asList(arr)); 
     int sum = priorityQueue.poll(); 
     int cost = 0; 
     while (!priorityQueue.isEmpty()) { 
      int currentElement = priorityQueue.poll(); 
      if (currentElement < sum) { 
       priorityQueue.add(sum); 
       sum = currentElement; 
      } else { 
       sum += currentElement; 
       cost += sum; 
       continue; 
      } 

      sum += priorityQueue.poll(); 
      cost += sum; 
     } 

     return new int[] {sum, cost}; 
    } 

es gibt sowohl die Summe und die Kosten für jede gegebene Array.

Bedingte Anweisung ein wenig uncessary gesehen kann aber es verbessert etwas unsere Laufzeit.