Javascript: Finden der minimalen Summe nach k Operationen

Question

Ein Array wird k-mal manipuliert, so dass jedes Mal der Maximalwert durch 2 geteilt und aufgerundet wird. Nach diesen k Manipulationen muss ich die minimale Summe finden. k und alle Zahlen im Array num> 1. Die Methode minSum empfängt ein Array namens num und eine ganze Zahl k. Der brutale Python-Code, der für mich mit sehr schlechter Zeitkomplexität funktioniert, ist:

function minSum(arr, k) {
    // Write your code here
let sum = 0; 
    while(k !==0){

       
        let max = Math.max(...arr)
        let index = arr.indexOf(max);
         
        max = Math.ceil(max/2);
        arr[index] = max;
        
        k--;
    }
    sum =  arr.reduce((a, b) => a + b, 0);
        console.log(sum);
    return sum;
}

Ähnliche Fragen beziehen sich auf Python ist hier. Effizientere Methode zum Ermitteln der minimalen Summe nach k Operationen

aber nichts im Zusammenhang mit Javascript.

Answer 1

Hier sind die Schritte (Verwenden von Java basierend auf Ihrer ersten Anforderung vor der Änderung von JavaScript):

• 1. Verwenden Sie den maximalen Heap (PriorityQueue in umgekehrter Reihenfolge), damit der maximale Wert oben liegt.
• 1. Für die Iteration: Holen Sie sich das Element oben (poll ()), führen Sie die Operation aus und fügen Sie es erneut zum maximalen Heap hinzu.
• 1. Am Ende nur Summe.

    public static int minSumJava_using_pqueue(int arr[], int k)
    {
        PriorityQueue<Integer> pq = new PriorityQueue<>(10, Collections.reverseOrder());

        for (int val : arr) {
            pq.add(val);
        }

        int new_val;
        for(int i =0; i<k; i++)
        {
            new_val = pq.poll();
            new_val = (int) Math.ceil(new_val/2.0);
            pq.add(new_val);
        }

        int sum = 0;
        for (Integer val: pq) {
            sum += val;
        }
        
        return sum;
    }

Überprüfen Sie den Quellcode:

    public static void main(String[] args)
    {
        int k = 4;
        int arr[] = {10,20,7};
        int result = minSumJava_using_pqueue(arr, k);
        System.out.println("min sum = "+ result);
    }

Das Ergebnis ist in der Tat das gleiche wie in Ihrem Beispiel:

min sum = 14

Hinweis: Mit JavaScript oder einer anderen Programmiersprache können Sie genau dasselbe tun .