Javascript: 找到 k 次操作后的最小总和

Question

一个数组被操作k次，每次最大值除以2并向上舍入。在这 k 次操作之后，我需要找到它的最小总和。 k 和数组 num > 1 中的所有数字。 minSum 方法接收一个名为 num 的数组和一个整数 k。对我来说时间复杂度非常低的粗暴 Python 代码是：

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 相关的类似问题。 More efficient method of finding minimum sum after k operations

但与 Javascript 无关。

Answer 1

以下是步骤（使用Java根据您在更改Java脚本之前的第一个需求）：

1. 使用最大堆（PriorityQueue倒序），所以最大堆在最前面
1. 第k次迭代：获取最顶层的元素（poll()），进行运算，再次加入最大堆
1. 最后，求和。

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

查看源代码：

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

结果确实和你的例子一样：

min sum = 14

注意：您可以使用 JavaScript 或任何其他编程语言做完全相同的事情。

Answer 2

const minSum = (arr, k) => {
  let newArr = arr
  while (k--) {
    let max;
    let newValue;
    let replacingIndex;
    max = Math.max.apply(Math, newArr);
    newValue = Math.ceil(max / 2);
    replacingIndex = newArr.findIndex((value) => value === max);
    newArr[replacingIndex] = newValue;
  }
  return newArr.reduce((a, b) => {a + b})
}

Javascript: 找到 k 次操作后的最小总和

Javascript: finding minimum sum after k operations

javascript

algorithm

time-complexity

space-complexity