Деление четных чисел на 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 для решения. Мы также проанализировали временную и пространственную сложность решения.
