力扣1675 数组的最小偏移量
1675. 数组的最小偏移量
给你一个由 n 个正整数组成的数组 nums 。
你可以对数组的任意元素执行任意次数的两类操作:
如果元素是 偶数 ,除以 2
例如,如果数组是 [1,2,3,4] ,那么你可以对最后一个元素执行此操作,使其变成 [1,2,3,2]
如果元素是 奇数 ,乘上 2
例如,如果数组是 [1,2,3,4] ,那么你可以对第一个元素执行此操作,使其变成 [2,2,3,4]
数组的 偏移量 是数组中任意两个元素之间的 最大差值 。
返回数组在执行某些操作之后可以拥有的 最小偏移量 。
示例 1:
输入:nums = [1,2,3,4]
输出:1
解释:你可以将数组转换为 [1,2,3,2],然后转换成 [2,2,3,2],偏移量是 3 - 2 = 1
示例 2:
输入:nums = [4,1,5,20,3]
输出:3
解释:两次操作后,你可以将数组转换为 [4,2,5,5,3],偏移量是 5 - 2 = 3
示例 3:
输入:nums = [2,10,8]
输出:3
提示:
n == nums.length
2 <= n <= 105
1 <= nums[i] <= 109
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimize-deviation-in-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int minimumDeviation(vector<int>& nums) {
set<int>s;
for(auto &nu : nums)
s.insert(nu % 2 ? nu * 2 : nu);
int res = *s.rbegin() - *s.begin();
while(*s.rbegin() % 2 == 0)
{
s.insert(*s.rbegin() / 2);
s.erase(*s.rbegin());
res = min(*s.rbegin() - *s.begin(), res);
}
return res;
}
};