1675. 数组的最小偏移量Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个由 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 * 10⁴
1 <= nums[i] <= 10⁹

# 思路

先把值都变成最大值，奇数*2，偶数不变。然后每次对最大的值/2，求差值，差值的最小值就是答案了

# 解法

class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int num : nums) {
            treeSet.add(num % 2 == 0 ? num : num * 2);
        }

        int cut = treeSet.last() - treeSet.first();
        while (cut > 0 && (treeSet.last() % 2 == 0)) {
            int value = treeSet.last();
            treeSet.remove(value);
            treeSet.add(value / 2);
            cut = Math.min(cut, treeSet.last() - treeSet.first());
        }
        return cut;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 总结

分析出几种情况，然后分别对各个情况实现

#Java