1775. Equal Sum Arrays With Minimum Number of Operations

又到了每周最傷心的周賽復盤時候

這題當下其實當下應該有往答案想過去了, 但卡在一個地方, 等等會說明

首先要先判別兩邊的長度, 分別為m, n

倘若m > 6 *n, 則直接回傳-1, why

 A:[1,1,1,1,1,1,1,1] B: [6]

可以看到就算B這個陣列用最大的值6, 他一定還是沒辦法達成已經全都是最小值的Ａ

反之 m < n * 6也可以直接回傳-1

再來我們將兩邊加總, 得到sum1, sum2

我們得致力於讓sum1, sum2相等, 這也是我想了好久的方向, 一度覺得不會從這邊切入

但其實還是可以的

為了不要一直要判斷sum1, sum2的大小, 我們統一讓sum1 < sum2

所以A這邊的陣列用min heap

B用max heap

為什麼呢, 因為sum2 > sum1, 所以我們傾向幫A最小的人加大, Ｂ最大的人縮小

大的願意縮小, 小的願意增大, 當小的(sum1)加大不小心加超過sum2, 即可收工

再來就是本作高潮的兩個點了

1. 到底要加大Ａ還是縮小B?

這個決定, 是依據看誰縮小放大幅度比較大做決定, 例如, A的最小是2, 等於我加大最多加4, B的最大是6, 等於我最多減5, 如果相等, 傾向縮小B, 所以會順便檢查B的heap 是否用完了

2. 怎樣可以到sum1 == sum2

這點我想超久, 後來發現, 根本不用在意

因為假設這個答案必定存在, 也就是我只要照個上方的流程, 當sum1 > sum2時,

我可以讓小的不要加那麼多, 或是大的不要減那麼多, 也就是只要達成上方條件就可以出來了

當下考慮太多了

這樣時間複雜度, 會是heap插入的操作 O(nlogn)

class Solution {
public:
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if(m > n * 6 || m * 6 < n) return -1;
        int sum1 = 0;
        int sum2 = 0;
        for(auto i: nums1){
            sum1+=i;
        }
        for(auto i: nums2){
            sum2+=i;
        }
        if(sum1==sum2) return 0;
        if(sum1 > sum2){
            return minOperations(nums2, nums1);
        }
        priority_queue<int, vector<int>, greater<>> pq1; //min queue
        for(int i: nums1){
            pq1.push(i);
        }
        priority_queue<int>pq2; // max queue
        for(int i: nums2){
            pq2.push(i);
        }
        int res = 0;
        while(sum1 < sum2){
            if(pq2.empty() || pq2.top() - 1 < 6 - pq1.top()){
                sum1 +=  6 - pq1.top();
                pq1.pop();
            }else{
                sum2 -= pq2.top() - 1;
                pq2.pop();
            }
            res++;
        }
        return res;
        
    }
};

另外還有一種greedy的做法, 因為值只會在1–6, 所以我們做兩個表, 分別存放出現次數, sum大的那個表, 我們就從他最大的數字開始砍, sum的的那個表, 我們就抓最小的數字開始加, 當差異從正的變成負的, 就代表找到那個值了

class Solution {
public:
    int findRes(int diff, vector<int> &table1, vector<int> &table2){
        int res = 0;
        for(int i = 1;i < 6 && diff > 0;i++){
            while(table1[7 - i] > 0 && diff > 0){
                diff-=6 - i;
                res++;
                table1[7 - i]--;
                
            }
            while(table2[i] > 0 && diff > 0){
                diff-=6 - i;
                res++;
                table2[i]--;
            }
        }
        return res;
    }
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if(m > n * 6 || m * 6 < n) return -1;
        int sum1 = 0;
        int sum2 = 0;
        vector<int> table1(7, 0);
        vector<int> table2(7, 0);
        for(auto i: nums1){
            sum1+=i;
            table1[i]++;
        }
        for(auto i: nums2){
            sum2+=i;
            table2[i]++;
        }
        if(sum1==sum2) return 0;
        if(sum1 > sum2){
            return findRes(sum1- sum2, table1, table2);
        }
        return findRes(sum2-sum1, table2, table1);
        
    }
};

時間複雜度為O(6 * max(m, n)) ~ O(max(m, n))