用 Python 编写程序最小化数组中的偏差

pythonserver side programmingprogramming更新于 2025/12/7 22:36:17

假设我们有一个数组 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 的最小元素
heapify nums
res := max_v - min_v
while 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))