数据结构
网络
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 次查看
广告