Javascript: k işleminden sonra minimum toplam bulma

Question

Bir dizi k kez işlenir, böylece her seferinde maksimum değer 2'ye bölünür ve yukarı yuvarlanır. Bu k manipülasyonlardan sonra minimum toplamını bulmam gerekiyor. k ve num> 1 dizisindeki tüm sayılar minSum yöntemi num adında bir dizi ve k tamsayısını alır. Benim için çok kötü zaman karmaşıklığıyla çalışan kaba Python kodu:

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;
}

Python ile ilgili benzer bir soru burada. K işleminden sonra minimum toplamı bulmanın daha verimli yöntemi

ancak Javascript ile ilgili hiçbir şey yok.

Answer 1

İşte adımlar (JavaScript'e geçişten önceki ilk talebinize göre Java'yı kullanarak):

• 1. Maksimum yığın kullanın (PriorityQueue ters sırada), böylece maksimum üstte olacaktır.
• 1. K iterasyonu için: üstteki öğeyi alın (anket ()), işlemi yapın ve maksimum yığına tekrar ekleyin.
• 1. Sonunda, sadece toplayın.

    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;
    }

Kaynak kodunu kontrol edin:

    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);
    }

Sonuç gerçekten sizin örneğinizdekiyle aynıdır:

min sum = 14

Not: JavaScript veya başka herhangi bir programlama dili ile tamamen aynı şeyi yapabilirsiniz .