X

LEETCODE 1675. Minimize Deviation in Array 解题思路分析

题目大意:

数组的最小偏移量

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1675

解题思路分析:

这些日子一直在忙项目,刷题的时间越来越少,感觉状态大不如前,总结一点就是,如果你打算去大厂面试,面试前一周甚至两周时间一定要坚持练习保持状态才可以。

言归正传,回到本题,题目要求求出偏差值(数组中最大值与最小值之差)最小的可能性,如果想让偏差值最小,那么我们需要不断地扩大数组中最小值,以及不断缩小最大值,直到最大值不能再缩小并且最小值不能再扩大为止,当前的偏差值即是最小情况。道理都懂,但实际操作起来确很麻烦,因为某个数字不断地变大再变小会使得情况变得非常复杂。所以我们应尽量将问题简单化。

对于本题,只有奇数可以扩大(乘2),但只限1次(因为扩大后会变成偶数),而偶数可以缩小1至n次,直到变为奇数为止。解题时,我们可以将所有奇数先变为偶数,即数组中的数字全部是偶数,这样一来,有两个好处:

  1. 我们只考虑减小某个数字即可。
  2. 每一次只考虑减小最大的偶数即可。(减小其他偶数并不会使得偏差值变得更小)

接下来思路就清晰了,我们来总结一下解题步骤

  1. 将数组中所有数字变成偶数,并使用PriorityQueue来存储所有偶数。
  2. 取出PriorityQueue中最大的数字,如果是偶数,将其减半再放回PriorityQueue中。如果是奇数,那么代表最大值无法再继续缩小,因此当前值与PriorityQueue中最小值之差即是返回结果。
  3. 通过步骤2不断更新PriorityQueue中数字,并维护数组中的最大值以及最小值,并通过最大值与最小值更新全局最小偏差值

实现代码:

public int minimumDeviation(int[] nums) {
    // 使用PriorityQueue由大到小排序数组中的数字
    PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
    // 最大值与最小值
    int max=0,min=Integer.MAX_VALUE;
    // 将数组中所有数字先变为偶数
    for(int n : nums){ // 循环每个数字
        if(n%2==1) n*=2; // 如果是奇数,先变为偶数
        if(n<min) min=n; // 更新最小值
        if(n>max) max=n; // 更新最大值
        q.offer(n);
    }
    int res = max - min; // 返回结果(最小偏差值)
    while(q.size()>0){
        int n = q.poll(); // 取出PriorityQueue中的最大值
        // 如果最大值为奇数,代表最大值无法再减小,退出
        if(n % 2 == 1) break;
        n /= 2; // 将当前数字除以2
        q.offer(n); // 将当前数字放回PriorityQueue中
        min=Math.min(min,n); // 用当前数字更新最小值
        max=q.peek(); // 用PriorityQueue中首元素更新最大值
        res = Math.min(res, max - min); // 更新最小偏差值
    }
    return res;
}

本题解法执行时间为80ms。

Runtime: 80 ms, faster than 77.85% of Java online submissions for Minimize Deviation in Array.

Memory Usage: 55 MB, less than 53.87% of Java online submissions for Minimize Deviation in Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1675-minimize-deviation-in-array-解题思路分析/
Categories: leetcode
kwantong: