1675. 数组的最小偏移量

https://leetcode-cn.com/problems/minimize-deviation-in-array/

对于偶数,它可以变为 (N, N/2, N/4 ...) , 而对于奇数,它可以变为 (N, 2*N) . 有两个不同的搜索方向,但是如果我们统一把奇数变为2*N的话,那么只有一个搜索方向(就是不断地除2)。期间我们只需要不断找到这个集合中,最大和最小值的差距即可。

从思想上看,从两个方向进行搜索(或者是两个维度上的单向搜索)是没有很好的办法找到最优解的,最好是将问题简化成为某一个方向上的搜索(或者是一个维度上的搜索)。

这个算法的时间复杂度是 O(32*n*lgn). 其中 32*n 可以理解为每个元素都会被整除32次,而lgn则表示树的时间复杂度。

class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> ts = new TreeSet<>();
        for (int x : nums) {
            if (x % 2 == 0) {
                ts.add(x);
            } else {
                ts.add(2 * x);
            }
        }
        int ans = ts.last() - ts.first();
        while (ans > 0 && ts.last() % 2 == 0) {
            int t = ts.last();
            ts.remove(t);
            ts.add(t / 2);
            int off = ts.last() - ts.first();
            ans = Math.min(ans, off);
        }
        return ans;
    }
}