2023-05-29：給你一個由 n 個正整數(shù)組成的數(shù)組 nums 你可以對數(shù)組的任意元素執(zhí)行任意
2023-05-29：給你一個由 n 個正整數(shù)組成的數(shù)組 nums
你可以對數(shù)組的任意元素執(zhí)行任意次數(shù)的兩類操作
如果元素是 偶數(shù) ，除以 2
例如，如果數(shù)組是 [1,2,3,4]
那么你可以對最后一個元素執(zhí)行此操作使其變成 [1,2,3,2]
如果元素是 奇數(shù) ，乘上 2
例如，如果數(shù)組是 [1,2,3,4] ，那么你可以對第一個元素執(zhí)行此操作，使其變成 [2,2,3,4]
數(shù)組的 偏移量 是數(shù)組中任意兩個元素之間的 最大差值。
返回數(shù)組在執(zhí)行某些操作之后可以擁有的 最小偏移量。
輸入：nums = [4,1,5,20,3]。
輸出：3。
答案2023-05-29：
大體步驟如下：
1.首先定義一個類型為?IntHeap?的結(jié)構(gòu)體，它實現(xiàn)了堆的基本操作，并重寫了 Less 方法以實現(xiàn)最大堆。
2.在?minimumDeviation()?函數(shù)中，創(chuàng)建一個空的?IntHeap?類型的堆?h，并使用給定的數(shù)據(jù)填充它。對于堆中的每個元素，如果它是奇數(shù)，則將其乘以 2 并插入堆中；否則，將其直接插入堆中。
3.初始化變量?res?為堆中最大元素與最小元素之差。
4.在一個 while 循環(huán)中，只要當前解仍可減小且堆中最大元素為偶數(shù)，就執(zhí)行以下操作：
??從堆中取出最大值?
curMax。??將?
curMax?除以 2 并插入堆中。??計算當前解并更新?
res。
5.返回變量?res?作為結(jié)果。
該算法的時間復雜度為 O(nlogn)，其中 n 是數(shù)組的長度。
在最壞情況下，我們需要對所有奇數(shù)元素乘以 2，因此數(shù)組中的每個元素最多會被操作兩次（一次除以 2，一次乘以 2）。這樣，我們就需要執(zhí)行 2n 次操作。由于堆的插入和刪除操作都需要 O(logn) 的時間，因此算法的總時間復雜度為 O(nlogn)。
該算法的空間復雜度為 O(n)，其中 n 是數(shù)組的長度。我們需要使用一個堆來存儲數(shù)組的所有元素，因此需要使用 O(n) 的額外空間。
go完整代碼如下：
package?main
import?(
????"container/heap"
????"fmt"
????"math"
)
type?IntHeap?[]int
func?minimumDeviation(nums?[]int)?int?{
????h?:=?IntHeap{}
????minVal?:=?math.MaxInt32
????for?i?:=?range?nums?{
????????if?nums[i]&1?==?1?{
????????????nums[i]?<<=?1
????????}
????????minVal?=?min(minVal,?nums[i])
????????heap.Push(&h,?nums[i])
????}
????res?:=?h[0]?-?minVal
????for?h[0]&1?==?0?{
????????curMax?:=?heap.Pop(&h).(int)
????????minVal?=?min(minVal,?curMax/2)
????????heap.Push(&h,?curMax/2)
????????res?=?min(res,?h[0]-minVal)
????}
????return?res
}
func?(h?IntHeap)?Len()?int???????????{?return?len(h)?}
func?(h?IntHeap)?Less(i,?j?int)?bool?{?return?h[i]?>?h[j]?}
func?(h?IntHeap)?Swap(i,?j?int)??????{?h[i],?h[j]?=?h[j],?h[i]?}
func?(h?*IntHeap)?Push(x?interface{})?{
????*h?=?append(*h,?x.(int))
}
func?(h?*IntHeap)?Pop()?interface{}?{
????old?:=?*h
????n?:=?len(old)
????x?:=?old[n-1]
????*h?=?old[0?:?n-1]
????return?x
}
func?min(a,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}
????return?b
}
func?main()?{
????nums?:=?[]int{4,?1,?5,?20,?3}
????fmt.Println(minimumDeviation(nums))
}
rust完整代碼如下：
use?std::cmp::Reverse;
use?std::collections::BTreeSet;
fn?minimum_deviation(nums:?Vec<i32>)?->?i32?{
????//?有序表，小?->?大?組織
????//?最大?set.last()
????let?mut?set?=?BTreeSet::new();
????for?num?in?nums?{
????????set.insert(if?num?%?2?==?0?{?num?}?else?{?num?*?2?});
????}
????//?答案
????let?mut?ans?=?set.iter().next_back().unwrap()?-?set.iter().next().unwrap();
????while?ans?>?0?&&?*set.iter().next_back().unwrap()?%?2?==?0?{
????????//?最大值
????????let?max?=?*set.iter().next_back().unwrap();
????????set.remove(&max);
????????set.insert(max?/?2);
????????ans?=?ans.min(set.iter().next_back().unwrap()?-?set.iter().next().unwrap());
????}
????ans
}
fn?main()?{
????let?nums?=?vec![4,?1,?5,?20,?3];
????let?result?=?minimum_deviation(nums);
????println!("{}",?result);
}
c++完整代碼如下：
using?namespace?std;
int?minimumDeviation(vector<int>&?nums)?{
????//?將奇數(shù)轉(zhuǎn)換為偶數(shù)
????for?(int&?num?:?nums)?{
????????if?(num?%?2?==?1)?{
????????????num?*=?2;
????????}
????}
????//?構(gòu)建有序集合
????multiset<int>?s(nums.begin(),?nums.end());
????//?答案
????int?ans?=?*s.rbegin()?-?*s.begin();
????while?(ans?>?0?&&?*s.rbegin()?%?2?==?0)?{
????????//?最大值
????????int?max_val?=?*s.rbegin();
????????s.erase(--s.end());
????????s.insert(max_val?/?2);
????????ans?=?min(ans,?*s.rbegin()?-?*s.begin());
????}
????return?ans;
}
int?main()?{
????vector<int>?nums?=?{?4,?1,?5,?20,?3?};
????cout?<<?minimumDeviation(nums)?<<?endl;?
????return?0;
}
c語言完整代碼如下：
//?比較兩個整數(shù)的大?。ㄓ糜?qsort?排序）
int?cmp(const?void*?a,?const?void*?b)?{
????return?*(int*)a?-?*(int*)b;
}
//?在有序數(shù)組中找到第一個大于等于?key?的元素的下標
int?lower_bound(int*?nums,?int?size,?int?key)?{
????int?left?=?0,?right?=?size,?mid;
????while?(left?<?right)?{
????????mid?=?left?+?(right?-?left)?/?2;?//?防止溢出
????????if?(nums[mid]?<?key)?{
????????????left?=?mid?+?1;
????????}
????????else?{
????????????right?=?mid;
????????}
????}
????return?left;
}
//?向右移動數(shù)組中指定范圍內(nèi)的元素
void?shift_right(int*?nums,?int?start,?int?end)?{
????for?(int?i?=?end;?i?>=?start;?--i)?{
????????nums[i?+?1]?=?nums[i];
????}
}
int?minimumDeviation(int*?nums,?int?numsSize)?{
????//?將奇數(shù)轉(zhuǎn)換為偶數(shù)
????for?(int?i?=?0;?i?<?numsSize;?++i)?{
????????if?(nums[i]?%?2?==?1)?{
????????????nums[i]?*=?2;
????????}
????}
????//?構(gòu)建有序集合
????int*?s?=?malloc(numsSize?*?sizeof(int));
????int?size?=?0;
????for?(int?i?=?0;?i?<?numsSize;?++i)?{
????????int?num?=?nums[i];
????????if?(num?%?2?==?0)?{
????????????s[size++]?=?num;
????????}
????????else?{
????????????s[size++]?=?num?*?2;
????????}
????}
????qsort(s,?size,?sizeof(int),?cmp);
????//?答案
????int?ans?=?s[size?-?1]?-?s[0];
????while?(ans?>?0?&&?s[size?-?1]?%?2?==?0)?{
????????//?最大值
????????int?max_val?=?s[--size];
????????s[size]?=?max_val?/?2;
????????int?insert_index?=?lower_bound(s,?size,?s[size]);
????????shift_right(s,?insert_index,?size?-?1);
????????s[insert_index]?=?max_val?/?2;
????????ans?=?min(ans,?s[size?-?1]?-?s[0]);
????}
????free(s);
????return?ans;
}
int?main()?{
????int?nums[]?=?{?4,?1,?5,?20,?3?};
????int?result?=?minimumDeviation(nums,?5);
????printf("%d\n",?result);?
????return?0;
}
