1675-数组的最小偏移量

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 11:06:46 2023-09-13 11:06:46 Updated    

给你一个由 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 <= 5 * 104
  • 1 <= nums[i] <= 109

参考并非常感谢大佬的解法 ，这里算是做一点补充。

方法和大佬方法一致，但是尝试用“遍历+剪枝”的思路来解释。因为“缩小最大值来优化”的说法有些模糊，因为缩小最大值的同时也可能改变了最小值，并不一定让结果更优，例如当前的值是[7,8],缩小最大值得到[7,4]，其实是让偏移量变大了，所以这里尝试用“遍历+剪枝”的思路来证明：

首先阐明几个点：

  1. 奇数只能乘一次: e.g. 3 -> 6 就不能再变大
  2. 偶数可以除多次: e.g. 8 -> 4 -> 2 -> 1
  • 所以每个数都有一个变化范围：e.g 原数字是3,它的变化范围就是[3,6],12的变化范围就是[3,6,12]
  • 所以其实原始问题等价于，“给定一系列变化范围[R1,R2…,Rn]，从每个变化范围中选择一个，使得偏移量最小”
  • 于是我们可以用遍历的思想来看待这个问题。但是这个问题的搜索空间是巨大的(R1*R2*…*Rn),所以需要剪枝

遍历过程（类似于“数学归纳法”）：

  1. 不妨从每个范围的最大可能值开始，假设当前的最大值ri(从Ri中取出)，最小值为rk。现在固定ri，遍历剩余范围的可能取值:
    此时其他值只能缩小，这只会使得最小值缩小，偏移增大，所以我们知道当Ri=ri时，最优解必定为一开始的ri-rk。于是Ri=ri的其他状态就都可以剪枝了，于是遍历完成Ri=ri的情况，将ri删掉，Ri变为ri/2
  2. 假设经历过t轮“将最大值除2”的遍历剪枝操作，当前的最大值是rj，最小值是ro。现在固定rj，遍历其它范围：
    对于Ro以外的范围，变大只可能让最大值变大，变小只可能让最小值变小，都比现在差，所以只用考虑ro(Ro)就行了，而且只用考虑ro*2就行了。如果ro是偶数，ro不能*2；如果ro是奇数，从前面的过程知道，Ro=ro必定是从Ro=ro*2的情况变来的，而Ro=ro*2的情况已经全部被遍历过了（被剪枝了）。所以，当Rj=rj时，最优解一定为一开始的rj-ro。于是Rj=rj的其他状态都可以剪枝了，于是遍历完Rj=rj的情况，将rj删掉，Rj变为rj/2
  3. 循环进行第2步，进行剪枝和遍历，并更新最优值。当最大值为奇数时，不能再/2，也就是剪枝剪掉了所有剩余情况，遍历完成

注：不可以先取所有范围的最小值，然后增大数值遍历，因为例如数字8，在降低到最小1后，只能再乘1次变到2,无法变回8,除非额外存储原数值

Python实现：

1
2
3
4
5
6
7
8
9
10
11
12
import heapq
class Solution:
    def minimumDeviation(self, nums: List[int]) -> int:
        nums = [-v*2 if v%2 else -v for v in nums] # heqpq构造维护最小堆
        min_value = -max(nums)
        heapq.heapify(nums)
        ans = -nums[0]-min_value # 当前最小偏移
        while not nums[0]%2: # 最大值为偶数
            min_value = min(min_value,-nums[0]/2)
            heapq.heapreplace(nums,nums[0]/2) # 最大值除2
            ans = min(ans,-nums[0]-min_value) # 更新最小偏移值
        return int(ans)
 Comments
On this page
1675-数组的最小偏移量