資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python 陣列最小偏差程式
假設我們有一個數組 nums。我們可以對陣列中的任何元素執行兩種型別的操作任意次數
對於偶數元素，將其除以 2
對於奇數元素，將其乘以 2。
現在陣列的偏差是陣列中任意兩個元素之間的最大差值。我們必須找到執行一些操作後陣列可以具有的最小偏差。因此，如果輸入類似於 nums = [6,3,7,22,5]，則輸出將為 5，因為我們可以在一次操作中將陣列設為 [6,6,7,22,5]，在第二次操作中設為 [6,6,7,22,10]，在另一次操作中設為 [6,6,7,11,10]，現在偏差為 11-6 = 5。
為了解決這個問題，我們將遵循以下步驟 -
對列表 nums 進行排序
max_v := nums 的最大元素
min_v := nums 的最小元素
將 nums 堆化
res := max_v - min_v
當 nums[0] 為奇數時，執行以下操作
v := 從堆佇列 nums 中彈出的元素
v := 2 * v
將 v 插入堆佇列 nums
min_v := nums[0]
max_v := v 和 max_v 的最大值
res := res 和 (max_v - min_v) 的最小值
nums := n 中所有數字的列表，並按負序排列
將堆佇列 nums 堆化
當 nums[0] 為偶數時，執行以下操作
v := -(從堆佇列 nums 中彈出的元素)
v := (v/2) 的商
將 -v 插入堆佇列 nums
max_v := -nums[0]
min_v := min_v 和 v 的最小值
res := res 和 (max_v - min_v) 的最小值
返回 res
示例
讓我們看看以下實現以獲得更好的理解
import heapq
def solve(nums):
nums.sort()
max_v,min_v = nums[-1],nums[0]
heapq.heapify(nums)
res = max_v-min_v
while nums[0]%2==1:
v = heapq.heappop(nums)
v = 2 * v
heapq.heappush(nums, v)
min_v = nums[0]
max_v = max(v, max_v)
res = min(res, max_v - min_v)
nums = [-n for n in nums]
heapq.heapify(nums)
while nums[0]%2==0:
v = -heapq.heappop(nums)
v = v // 2
heapq.heappush(nums, -v)
max_v = -nums[0]
min_v = min(min_v,v)
res = min(res, max_v - min_v)
return res
nums = [6,3,7,22,5]
print(solve(nums))輸入
[6,3,7,22,5]
輸出
5
更新於: 2021年10月7日
470 次檢視
廣告