Hard
,Array
,Greedy
,Heap
1675. Minimize Deviation in Array
You are given an array nums
of n
positive integers.
You can perform two types of operations on any element of the array any number of times:
2
.
[1,2,3,4]
, then you can do this operation on the last element, and the array will be [1,2,3,2]
.2
.
[1,2,3,4]
, then you can do this operation on the first element, and the array will be [2,2,3,4]
.The deviation of the array is the maximum difference between any two elements in the array.
Return the minimum deviation the array can have after performing some number of operations.
Example 1:
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.
Example 2:
Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.
Example 3:
Input: nums = [2,10,8]
Output: 3
Constraints:
n
== nums.length
n
<= 5 * 104nums[i]
<= 109
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
int min_v = INT_MAX, res = INT_MAX;
priority_queue<int> q;
for(int i = 0; i < nums.size(); i++)
{
nums[i] = nums[i]&1 ? nums[i]*2 : nums[i];
min_v = min(min_v, nums[i]);
q.push(nums[i]);
}
res = q.top() - min_v;
while(q.top() % 2 == 0)
{
int v = q.top()/2; q.pop();
q.push(v);
min_v = min(min_v, v);
res = min(res, q.top()-min_v);
}
return res;
}
};
Time: n
次, 每次push一個值進priority queue
Extra Space:
XD Feb 24, 2023
跟天宇一樣,但考慮到數字是
Runtime 602ms (Beats 38.66%)
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
int lower = INT_MAX;
priority_queue<int> pq;
for (int i = 0; i < nums.size(); i++) {
nums[i] <<= nums[i] & 1;
lower = min(lower, nums[i]);
pq.push(nums[i]);
}
int ans = pq.top() - lower;
while (pq.top() % 2 == 0) {
int value = pq.top() / 2;
pq.pop();
pq.push(value);
lower = min(lower, value);
ans = min(ans, pq.top() - lower);
}
return ans;
}
};
Yen-Chi ChenSat, Feb 25, 2023
利用set來減少相同的數字重複檢查,複雜度一樣是
Runtime 333ms (Beats 89.8%)
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
int lower = INT_MAX;
set<int> s;
for (int i = 0; i < nums.size(); i++) {
nums[i] <<= nums[i] & 1;
lower = min(lower, nums[i]);
s.insert(nums[i]);
}
int ans = *s.rbegin() - lower;
while (*s.rbegin() % 2 == 0) {
int value = *s.rbegin();
s.erase(value);
value = value / 2;
s.insert(value);
lower = min(lower, value);
ans = min(ans, *s.rbegin() - lower);
}
return ans;
}
};
Yen-Chi ChenSat, Feb 25, 2023
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
int max_odd = 1;
for (auto num : nums) {
while (num % 2 == 0) num >>= 1;
max_odd = max(max_odd, num);
}
for (auto& num : nums) {
if (num % 2 == 0) {
num >>= 1;
while (num > max_odd) num >>= 1;
}
}
sort(nums.begin(), nums.end());
int ans = max_odd - nums[0], n = nums.size();
for (int i = 0; i < n - 1; i++) {
ans = min(ans, max(max_odd, nums[i] * 2) - min(nums[i+1], nums[0] * 2));
}
return ans;
}
};
Yen-Chi ChenSat, Feb 25, 2023
function minimumDeviation(nums) {
const maxHeap = new MaxHeap();
let min = Infinity;
for (const num of nums) {
if (num % 2 === 1) {
maxHeap.push(num * 2);
min = Math.min(min, num * 2);
} else {
maxHeap.push(num);
min = Math.min(min, num);
}
}
let result = maxHeap.top() - min;
while (maxHeap.top() % 2 === 0) {
const max = maxHeap.pop();
min = Math.min(min, max / 2);
maxHeap.push(max / 2);
result = Math.min(result, maxHeap.top() - min);
}
return result;
}
// Priority Queue
class MaxHeap {
constructor() {
this.queue = [];
}
push(val) {
this.queue.push(val);
this.bubbleUp();
return this;
}
pop() {
const val = this.queue[0];
const last = this.queue.pop();
if (this.queue.length > 0) {
this.queue[0] = last;
this.bubbleDown();
}
return val;
}
top() {
return this.queue[0];
}
bubbleUp() {
let index = this.queue.length - 1;
let parentIndex = ~~((index - 1) / 2);
while (this.queue[index] > this.queue[parentIndex]) {
[this.queue[index], this.queue[parentIndex]] = [this.queue[parentIndex], this.queue[index]];
index = parentIndex;
parentIndex = ~~((index - 1) / 2);
}
return this;
}
bubbleDown() {
let index = 0;
let leftIndex = index * 2 + 1;
let rightIndex = index * 2 + 2;
let maxIndex = index;
while (leftIndex < this.queue.length) {
if (this.queue[leftIndex] > this.queue[maxIndex]) {
maxIndex = leftIndex;
}
if (rightIndex < this.queue.length && this.queue[rightIndex] > this.queue[maxIndex]) {
maxIndex = rightIndex;
}
if (maxIndex === index) break;
[this.queue[index], this.queue[maxIndex]] = [this.queue[maxIndex], this.queue[index]];
index = maxIndex;
leftIndex = index * 2 + 1;
rightIndex = index * 2 + 2;
}
return this;
}
}
參考樓上兩位大神的方法1,先寫個max heap練習一下,結果錯了好幾次…
MarsgoatMar 2, 2023