讨论/《春招冲刺班 - 7 天刷题挑战》 - 1675. 数组的最小偏移量/
《春招冲刺班 - 7 天刷题挑战》 - 1675. 数组的最小偏移量
共 4 个回复

这道题的思路:
问题求解数组中最大值和最小值的差值最小。
给出的操作条件可以看出:
- (奇数 * 2),只能对每个奇数操作一次。
- (偶数 / 2),则可以对每个偶数操作多次。
要使最大值与最小值的差值最小,一个简单的想法是,让最小值变大,让最大值变小。

  1. 完成最小值变大。又因为 奇数操作仅仅能做1次,则 (奇数 * 2) = 偶数,可以使用 (偶数 / 2)= 原奇数。因此,可以放心大胆的将奇数执行 (奇数 * 2)的操作,将可能存在的小值变大,即使可能存在奇数值乘于2后变大对结果没有贡献,但可以通过偶数操作,恢复成原奇数。
    最小值的获取,可以在对nums数组进行遍历操作时获得,并在最大值变小时进行维护。
  2. 完成最大值变小。剩下的只需要把最大的偶数值执行(偶数 / 2)的操作即可;若最大值为奇数,则无法继续变小,循环结束。
    最大值的获取,每次取出最大值,可以使用优先队列(堆)来实现。
  3. 差值的最小,可能存在于上述变换的某个状态中,因此需要不断更新最小的差值。
class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        priority_queue<int, vector<int>, less<int>> large_queue;

        int min_value = INT_MAX;
        for (auto &num : nums)
        {
            num = num & 1 ? num * 2 : num;
            large_queue.push(num);
            min_value = min(min_value, num);
        }
        int offset = INT_MAX, largest_num;
        while (large_queue.top() % 2 == 0)
        {
            offset = min(offset, large_queue.top() - min_value);
            largest_num = large_queue.top();
            largest_num /= 2;
            large_queue.pop();
            large_queue.push(largest_num);
            min_value = min(min_value, largest_num);
        }
        offset = min(offset, large_queue.top() - min_value);

        return offset;
    }
};
3

思路:让最小值尽可能大,让最大值尽可能小
由于增大只有奇数才能够进行,因而先对所有奇数*2
然后对偶数进行尽可能小
代码如下:

class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for(int num : nums)
            set.add(num % 2 == 0? num : num * 2);
        int res = set.last() - set.first();
        while(res > 0 && set.last() % 2 == 0){
            int val = set.last();
            set.remove(val);
            set.add(val / 2);
            res = Math.min(res, set.last() - set.first());
        }
        return res;
    }
}
2

高中的时候写过这道题,就直接copy pasta上去了
so basically 建两个数组,一个数组用minNum来装nums.at(i)的最小值(i.e.如果是奇数就不变,如果是偶数就除以二,除到为奇数为止),另一个数组maxNum用来装nums.at(i)的最大值(i.e.如果是奇数就乘二,如果是偶数就不变)。然后再以pair的形式按顺序把minNum.at(i)和maxNum.at(i)装入一个新的vector sort,那么,当我们找到一个minNum.at(i),就可以找到它对应的上限(或最大值)。
所以我们sort一遍,这个sort先把minNum从大到小排序好,在minNum相同的情况下把maxNum从大到小排好。(可能表述有点不清,意思就是如果说minNum(i)被排到了第j位,maxNum(i)也被排到了第j位,因为他们成pair)(不知道c++是怎么做到的但就是好酷)
举个栗子,nums为[1,2,3,4],minNum为[1,1,3,1],maxNum为[2,2,6,4],sorted为[(1,2),(1,2),(1,4),(1,6)]
intuitively我们想让这个nums里的数字越小越好,比如说nums为[1,2],变化成[1,1]是比[2,2]是要更优的。
我们先记录目前情况下的最小差curDiff,sorted的尾减sorted的头就行了,再记录目前的最大值curMax,which is sorted的尾。
注意,sorted[i].first对应的是minNum.at(i),sorted[i].second对应的是maxNum.at(i)。为了方便理解,下文将用minNum.at(i)指代sorted[i].first。
我们从sort的第0位开始,loop到倒数第1位。我们知道每一个minNum.at(i)是尽可能小的,所以它只有上升空间,且上升空间为maxNum.at(i),要提醒一点的就是我们不想让这个数超越curMax,所以curMax也是个上限。如果这个数有上升空间,那就尽管地乘。可以理解成一堆柱状图,从低到高排好,如果第i个柱子能乘二但不会高于最高的那一根,那尽管地乘,因为那样它与最高的柱子差距会更小。
最后一步要考虑的是如果是,如果第0位乘2后,虽然高于最高的那一根,但这个sorted里最小值却变小了,并且会有更优解。例如现在是[3,5],如果3乘上2,[6,5]岂不是会产生更好的答案?为了解决这个问题,先记录当下的最优解,找到curMax和curMin并更新curDiff。loop一遍这个sorted,如果(minNum.at(i)还有上升空间,且minNum.at(i+1)与它相同),continue,因为两个数字都可以越过curMax,且后者的上限大于等于前者。如果(minNum.at(i)还有上升空间,且minNum.at(i+1)与它不同),假设它乘2,minNum.at(i+1)就是新的下限curMin了,这时候看看乘了2的minNum.at(i) - curMin是不是会产生更小的curDiff,如果是的话就,就把curMax更新为minNum.at(i) * 2。如此循环,如果说第i位没有上升空间了,那不好意思,不给鸡会了,break。

最后return curDiff

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        vector<int> minNums, maxNums;
        for(auto i = nums.begin(); i != nums.end(); ++i){
            if(* i % 2 == 1){
                minNums.push_back(*i);
                maxNums.push_back(*i * 2);
            }
            else{
                maxNums.push_back(*i);
                while(*i % 2 != 1){
                    *i /= 2;
                }
                minNums.push_back(*i);
            }
        }
        //sort 2 vect
        vector<pair <int,int>> sorted;
        for(int i = 0; i < nums.size(); i++){
            sorted.push_back(make_pair(minNums.at(i), maxNums.at(i)));
        }
        sort(sorted.begin(), sorted.begin() + sorted.size());
        int curMin = sorted[0].first, curMax = sorted[sorted.size() - 1].first;

        
/*        for(int i = 0; i < nums.size(); i++){
            cout << sorted[i].first << " ";
        }
        cout << endl;*/
        //double up!
        for(int i = 0; i < nums.size() - 1; i++){
            while(sorted[i].first * 2 < curMax && sorted[i].first * 2 <= sorted[i].second){
                sorted[i].first *= 2;
            }
        }
        


        curMin = INT_MAX;
        for(int i = 0; i < nums.size(); i++){
            if (sorted[i].first < curMin) curMin = sorted[i].first;
        }
        int curDiff = curMax - curMin;
        sort(sorted.begin(), sorted.begin() + sorted.size());
        curDiff = sorted[sorted.size() - 1].first - sorted[0].first;
        
  /*      for(int i = 0; i < nums.size(); i++){
            cout << sorted[i].first << " ";
        }cout << endl; */
        
        for(int i = 0; i < nums.size() - 1; i++){
            if(sorted[i].first * 2 <= sorted[i].second){
                if(sorted[i].first == sorted[i+1].first){
                    continue;
                }
                else if(sorted[i].first * 2 - curMax <= curDiff && sorted[i].first * 2 - sorted[i+1].first <= curDiff) {
                    curDiff = max(sorted[i].first * 2 - sorted[i+1].first,sorted[i].first * 2 - curMax);
                    curMax = sorted[i].first * 2;
                    sorted[i].first *= 2;
   //                 curMax = sorted[i].first;
   //                 curMin = sorted[i+1].first;      
                }
            }
            else break;
        }
        

        
        
/*      
        for(int i = 0; i < nums.size(); i++){
            cout << sorted[i].first << " ";
        }*/
        
        return curDiff;
/*
[4,1,5,20,3,14,3,4,37]
[1,31]
[4,1,5,20,3]
[1,2,3,4]
[3,5]
[10,4,3]
[399,908,648,357,693,502,331,649,596,698,698]
*/
    }
};

对了我的表达不是很清晰,希望有大佬能看懂并简介化一下我的思路 qwq

1

参与“7天刷题挑战”的童鞋欢迎点击问卷加入专属社群哦~
2月1日-7日,字节跳动工程师直播刷题等你来围观