This approach utilizes a max-heap to efficiently retrieve the largest element while adjusting it within the array to reduce deviation.
1. First, we convert all numbers to even (since an odd number can only become larger when even via multiplication). This is done by multiplying odd numbers by 2.
2. We utilize a max-heap where each iteration involves reducing the maximum number (if even) to reduce the deviation.
3. Throughout this process, track the minimum seen number to calculate and update the minimum deviation at every stage.
Time Complexity: O(n log n) due to sorting operations on each iteration.
Space Complexity: O(n) for the heap structure representation.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int MinimumDeviation(int[] nums) {
6 PriorityQueue<int, int> maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
7 int minVal = int.MaxValue;
8
9 foreach (var num in nums) {
10 var newValue = num % 2 == 1 ? num * 2 : num;
11 minVal = Math.Min(minVal, newValue);
12 maxHeap.Enqueue(newValue, newValue);
13 }
14
15 int minDeviation = int.MaxValue;
16
17 while (maxHeap.Count > 0) {
18 int maxVal = maxHeap.Dequeue();
19 minDeviation = Math.Min(minDeviation, maxVal - minVal);
20 if (maxVal % 2 == 1) break;
21 maxVal /= 2;
22 minVal = Math.Min(minVal, maxVal);
23 maxHeap.Enqueue(maxVal, maxVal);
24 }
25
26 return minDeviation;
27 }
28}This C# solution involves using a priority queue to keep track of the largest element, which is continually reduced to improve the smallest deviation. Operations are performed only on the maximal element derived from the queue.
The function halts processing for odd maximal values, outputting minimized deviation.
In this alternative approach, the strategy focuses on an incremental adjustment instead of heap reliance. It involves directly mutating and managing the adjustment in a sorted sequence approach to target deviation reduction without standard heap operations.
1. First, transform any odd number by doubling it. Track the preliminary minimum number.
2. Sort the array and iteratively adjust the maximum through division by halving until reaching an odd number.
The minimum deviation is kept through direct comparison evaluations across the deviations achieved after each max adjustment.
Time Complexity: O(n^2 log n) due to multiple sorts.
Space Complexity: O(1) or O(n) considering in-place sorts might not require extra space.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int minimumDeviation(vector<int>& nums) {
8 for (auto &num : nums)
9 if (num % 2 == 1) num *= 2;
10
11 sort(nums.begin(), nums.end());
12 int minDeviation = nums.back() - nums.front();
13
14 while (nums.back() % 2 == 0) {
15 nums.back() /= 2;
16 sort(nums.begin(), nums.end());
17 minDeviation = min(minDeviation, nums.back() - nums.front());
18 }
19
20 return minDeviation;
21}This C++ method establishes deviation reduction by direct manipulation within a sorting framework, enhancing deviation tracking without reliance on a priority queue.
It leverages basic direct list sorting after direct maximal element alterations.