Leetcode 问题 1675：最小化数组中的偏差

偶数除以2和奇数乘以2

介绍 在这个问题中，我们得到了一个正整数数组，我们可以对数组的任何元素执行任意次数的两种类型的操作。我们需要最小化数组的偏差，这是数组中任意两个元素之间的最大差异。

方法 我们可以使用最大堆来跟踪数组中的最大元素。我们首先将数组中的所有元素相乘，直到它们变成奇数。然后我们寻找数组中最小的元素并将其除以 2。我们重复这个过程，直到我们不能再将任何元素除以 2。我们计算每一步的偏差并跟踪最小偏差。到达终点后，我们返回最小偏差。

代码 下面是解决方案的 JavaScript 代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDeviation = function(nums) {
    let heap = new MaxHeap();
    let minDeviation = Infinity;
    let min = Infinity;
    for(let i=0; i<nums.length; i++){
        if(nums[i]%2 !== 0){
            nums[i] *= 2;
        }
        heap.insert(nums[i]);
        min = Math.min(min, nums[i]);
    }
    while(true){
        let max = heap.extractMax();
        minDeviation = Math.min(minDeviation, max-min);
        if(max%2 === 1){
            break;
        }else{
            heap.insert(max/2);
            min = Math.min(min, max/2);
        }
    }
    return minDeviation;
};

class MaxHeap {
    constructor(){
        this.heap = [];
    }
    insert(value){
        this.heap.push(value);
        this.bubbleUp();
    }
    bubbleUp(){
        let index = this.heap.length-1;
        while(index > 0){
            let parentIndex = Math.floor((index-1)/2);
            if(this.heap[parentIndex] < this.heap[index]){
                [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
                index = parentIndex;
            }else{
                break;
            }
        }
    }
    extractMax(){
        if(this.heap.length === 1){
            return this.heap.pop();
        }else{
            let max = this.heap[0];
            this.heap[0] = this.heap.pop();
            this.sinkDown(0);
            return max;
        }
    }
    sinkDown(index){
        let left = 2*index+1;
        let right = 2*index+2;
        let largest = index;
        if(left < this.heap.length && this.heap[left] > this.heap[largest]){
            largest = left;
        }
        if(right < this.heap.length && this.heap[right] > this.heap[largest]){
            largest = right;
        }
        if(largest !== index){
            [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
            this.sinkDown(largest);
        }
    }
    peek(){
        return this. Heap[0];
    }
}

复杂性分析

• 时间复杂度：O(n*log(m))，其中n是数组的长度，m是数组中的最大元素。
• 空间复杂度：O(n)，因为我们使用堆来存储数组中的元素。

结论

在这篇博文中，我们讨论了 Leetcode 问题 1675：最小化数组中的偏差。我们已经解释了我们的方法并提供了解决方案的 JavaScript 代码。我们还分析了解决方案的时间和空间复杂度。