题目描述
给你一个由 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 <= 10^5
1 <= nums[i] <= 10^9
算法1
(数学,中心缩放) $O(n * max(logn, logS))$, $S为nums[i]的大小$
- 我们证明一个结论:生成答案的序列中,一定包含数组中所有数能生成的最大奇数(可能是自己,可能是偶数/2),记录为
maxOdd
。- 如果最终序列都是偶数,那么他们同时除以2,偏移量一定会变小,因此可以对全是偶数的数组无限除以2,最终必有一个数是奇数。
- 假设数组中有一个大偶数
e
,e/2 >=当前最大的奇数
, 那么我们让e/2
一定不会使偏移量变大。e
可以无限除2
,最终得到一个奇数,这时maxOdd
就是这个奇数和之前奇数中大的一个 - 因此 最终生成的答案数组中,所有数值能生成的最大奇数一定在其中。
- 因此, 我们可以遍历数组,找到整个数组的
maxOdd
, - 我们可以对记录所有的数字可以变换到的值的最小和最大值
minV
和maxV
,例如,100
的minV
是25
,maxV
是100
,15
的minV
=15
,maxV
=30
. - 如果可以, 将所有数字缩放到 $[maxOdd / 2 + 1, maxOdd]$之间,因为
maxOdd
一定在序列中,那么答案一定在数值在$[maxOdd / 2 + 1, maxOdd * 2]$的数对中产生,否则,记录无法缩放的数字的最小值minNum
,答案为maxOdd - minNum
. - 映射后排序,会生成形如$[x_1, x_2, x_3,…, maxOdd]$的数组, $x_1 <= x_2 <= x_3 <= … <= maxOdd$, 由于映射关系,一定有从前往后枚举到$x_i$时, 如果$x_i * 2 <= maxV_i$, 那么$x_i * 2$是当前序列最大值, $x_{i+1}$是最小值,尝试更新答案. 如果 $x_i * 2 > maxV_i$, 那么 $x_i$一定是最终答案序列中的最小值, 可以直接退出循环。
- 样例解释:
- 输入
nums=[98, 99, 100]
- 找到
maxOdd
=99
- 找到所有数的
minV
和maxV
,$98:[49, 98], 99: [99, 198], 100:[25, 100]$ - 将所有数映射到 $[50, 99]$之间并排序: $[50, 98, 99]$, 初始化
ans
=49
; - 枚举映射数组,
50 * 2
在[25, 100]
之间,此时数组变成[100, 98, 99]
,ans = 100 - 98 = 2
98 * 2
超出了98
所对应的maxV
, 说明98
一定是最终数组的最小值,停止循环。- 此时答案为
2
- 输入
时间复杂度
- 预处理找出
maxOdd
需要$O(n)$的时间 - 预处理每个数的
minV
和maxV
需要$O(nlogS)$的时间, - 缩放所有数字到目标区间需要 $O(nlogS)$
- 对映射数组排序需要$nlogn$的时间
- 遍历数组缩放映射后的值尝试更新答案需要$O(n)$的时间
- 故总时间复杂度为 $O(n * max(logn, logS))$;
C++ 代码
struct Node{
int x, minV, maxV;
bool operator < (const Node& b) const{
return x < b.x;
}
};
class Solution {
public:
Solution(){
cin.tie(0);
ios::sync_with_stdio(0);
}
int minimumDeviation(vector<int>& nums) {
int n = nums.size();
vector<Node> CYY(n);
bool exit = false;
int minDelta, minNum = 2e9, maxOdd = -1;
for(int i = 0; i < n; i++){
if (nums[i] & 1) {
CYY[i] = {0, nums[i], nums[i] * 2};
maxOdd = max(maxOdd, nums[i]);
}else{
int t = nums[i];
while(t % 2 == 0) t/= 2;
CYY[i] = {0, t, nums[i]};
maxOdd = max(maxOdd, t);
}
}
int threshold = maxOdd / 2 + 1;
for (int i = 0; i < n; i++){
int num = CYY[i].minV;
while( num <= CYY[i].maxV && num < threshold) num*=2;
if (num >= threshold && num <= CYY[i].maxV){
CYY[i].x = num;
}else{
minNum = min(minNum, CYY[i].maxV);
exit = true;
}
}
if(exit) return maxOdd - minNum;
sort(CYY.begin(), CYY.end());
minDelta = CYY[n - 1].x - CYY[0].x;
for(int i = 0; i < n - 1; i ++){
if(CYY[i].x * 2 <= CYY[i].maxV) minDelta = min(minDelta, CYY[i].x * 2 - CYY[i + 1].x);
else break;
}
return minDelta;
}
};