1675. Minimize Deviation in Array

leetcode hard

#array#csharp#hard#heap#leetcode#math#queue

Task

Вам дан массив nums из n положительных целых чисел.

Вы можете выполнять два типа операций над любым элементом массива любое количество раз:

Если элемент четный, разделите его на 2.

Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на последнем элементе, и массив станет [1,2,3,2].

Если элемент нечетный, умножьте его на 2.

Например, если массив [1,2,3,4], то вы можете выполнить эту операцию на первом элементе, и массив станет [2,2,3,4].

Отклонение массива — это максимальная разница между любыми двумя элементами в массиве.

Верните минимальное отклонение, которое может иметь массив после выполнения некоторого числа операций.

Пример:

Input: nums = [1,2,3,4]

Output: 1

Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int MinimumDeviation(int[] nums) {
        var evens = new PriorityQueue<int>();
        int minimum = int.MaxValue;
        
        foreach (var num in nums) {
            if (num % 2 == 0) {
                evens.Enqueue(num);
                minimum = Math.Min(minimum, num);
            } else {
                evens.Enqueue(num * 2);
                minimum = Math.Min(minimum, num * 2);
            }
        }
        
        int minDeviation = int.MaxValue;
        
        while (evens.Count > 0) {
            int currentValue = evens.Dequeue();
            minDeviation = Math.Min(minDeviation, currentValue - minimum);
            if (currentValue % 2 == 0) {
                evens.Enqueue(currentValue / 2);
                minimum = Math.Min(minimum, currentValue / 2);
            } else {
                break;
            }
        }
        
        return minDeviation;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinimumDeviation(vector<int>& nums) {
        var evens = new PriorityQueue<int>();
        int minimum = int.MaxValue;
        
        foreach (var num in nums) {
            if (num % 2 == 0) {
                evens.Enqueue(num);
                minimum = min(minimum, num);
            } else {
                evens.Enqueue(num * 2);
                minimum = min(minimum, num * 2);
            }
        }
        
        int minDeviation = int.MaxValue;
        
        while (evens.size() > 0) {
            int currentValue = evens.Dequeue();
            minDeviation = min(minDeviation, currentValue - minimum);
            if (currentValue % 2 == 0) {
                evens.Enqueue(currentValue / 2);
                minimum = min(minimum, currentValue / 2);
            } else {
                break;
            }
        }
        
        return minDeviation;
    }
}

Java solution

matched/original

class Solution {
    public int minimumDeviation(int[] nums) {
        PriorityQueue<Integer> evens = new PriorityQueue<>(Collections.reverseOrder());
        int minimum = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num % 2 == 0) {
                evens.offer(num);
                minimum = Math.min(minimum, num);
            } else {
                evens.offer(num * 2);
                minimum = Math.min(minimum, num * 2);
            }
        }
        int minDeviation = Integer.MAX_VALUE;

        while (!evens.isEmpty()) {
            int currentValue = evens.poll();
            minDeviation = Math.min(minDeviation, currentValue - minimum);
            if (currentValue % 2 == 0) {
                evens.offer(currentValue / 2);
                minimum = Math.min(minimum, currentValue / 2);
            } else {
                break;
            }
        }
        return minDeviation;
    }
}

Python solution

matched/original

import heapq

class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        evens = []
        minimum = float('inf')
        
        for num in nums:
            if num % 2 == 0:
                heapq.heappush(evens, -num)
                minimum = min(minimum, num)
            else:
                heapq.heappush(evens, -num * 2)
                minimum = min(minimum, num * 2)
        
        minDeviation = float('inf')
        
        while evens:
            currentValue = -heapq.heappop(evens)
            minDeviation = min(minDeviation, currentValue - minimum)
            if currentValue % 2 == 0:
                heapq.heappush(evens, -currentValue // 2)
                minimum = min(minimum, currentValue // 2)
            else:
                break
        
        return minDeviation

Go solution

matched/original

import (
    "container/heap"
    "math"
)

func minimumDeviation(nums []int) int {
    evens := &IntHeap{}
    heap.Init(evens)
    minimum := math.MaxInt32
    
    for _, num := range nums {
        if num % 2 == 0 {
            heap.Push(evens, num)
            if num < minimum {
                minimum = num
            }
        } else {
            heap.Push(evens, num * 2)
            if num * 2 < minimum {
                minimum = num * 2
            }
        }
    }
    
    minDeviation := math.MaxInt32
    
    for evens.Len() > 0 {
        currentValue := heap.Pop(evens).(int)
        if currentValue - minimum < minDeviation {
            minDeviation = currentValue - minimum
        }
        if currentValue % 2 == 0 {
            heap.Push(evens, currentValue / 2)
            if currentValue / 2 < minimum {
                minimum = currentValue / 2
            }
        } else {
            break
        }
    }
    
    return minDeviation
}

type IntHeap []int

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

Explanation

Algorithm

Инициализируйте max-heap под названием evens. Если элемент массива четный, добавьте его в evens; если элемент нечетный, умножьте его на 2 и добавьте в evens. Одновременно отслеживайте минимальный элемент в evens.

Извлекайте максимальный элемент из evens, обновляйте минимальное отклонение, используя максимальный элемент и текущий минимальный элемент. Если максимальный элемент четный, делите его на 2 и снова добавляйте в evens.

Повторяйте шаг 2 до тех пор, пока максимальный элемент в evens не станет нечетным. Верните минимальное отклонение.

😎