1675 Minimize Deviation in Array

Leetcode

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

If the element is even, divide it by 2.
For example, if the array is [1,2,3,4], then you can do this operation on the last element, and the array will be [1,2,3,2].
If the element is odd, multiply it by 2.
For example, if the array is [1,2,3,4], then you can do this operation on the first element, and the array will be [2,2,3,4].
The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Example 1:

Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.

Example 2:

Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

Example 3:

Input: nums = [2,10,8]
Output: 3

---

奇数只能乘以一次 2 ，而偶数可以除以多次 2 ，直到为奇数。把奇数都乘以 2 （之后如果需要还可以变回来），然后把所有数放在一个 TreeSet 里，实现自动去重，而且可以获取最大和最小值。根据最大最小值计算差值，然后取出最大值，如果是偶数除以 2 ，放入 set ，再计算最小值，不断重复。最小值一定会在这个过程中出现。

public int minimumDeviation(int[] nums) {
    if(nums==null || nums.length==0) return 0;
    TreeSet<Integer> set=new TreeSet<>();
    for(int i:nums){
        if( (i & 1) == 1){
            i = i << 1;
        }
        set.add(i);
    }
    int min=set.last()-set.first();
    int max=set.last();
    while((max & 1) ==0){
        set.remove(max);
        max = max>>1;
        set.add(max);
        max=set.last();
        int i=set.last()-set.first();
        if(i<min) min=i;
    }
    return min;
}

也可以使用优先队列（大顶堆），另外需要一个变量记录最小值。

public int minimumDeviation(int[] nums) {
    if(nums==null || nums.length==0) return 0;
    PriorityQueue<Integer> pq = new PriorityQueue<>((i1, i2)->i2-i1);
    int min=Integer.MAX_VALUE;
    for(int i:nums){
        if((i & 1) == 1){
            i=i<<1;
        }
        if(i<min) min=i;
        pq.add(i);
    }
    int max=pq.peek();
    int ret=max-min;
    while((max & 1) ==0){
        max=pq.poll()>>1;
        if(max<min) min=max;
        pq.add(max);
        max=pq.peek();
        if(pq.peek()-min<ret) ret=pq.peek()-min;
    }
    return ret;
}