Share my 0ms CPP solution


  • 1
    J
    class Solution {
    public:
        void findAndRemoveOppositePair(map<int, int>& mm, int& res) {
            vector<int> removeVal;
            auto it = mm.begin();
            while(it != mm.end()) {
                int val = it->first;
                if(mm[val] > 0 && mm.find(-val) != mm.end() && mm[-val] > 0) {
                    if(--mm[val] == 0) removeVal.push_back(val);
                    if(--mm[-val] == 0) removeVal.push_back(-val);
                    res++;
                }
                it++;
            }
            
            for(int i = 0; i < removeVal.size(); i++) {
                mm.erase(removeVal[i]);
            }
            removeVal.clear();
        }
        
        int minTransfers(vector<vector<int>>& transactions) {
            if(transactions.empty()) return 0;
            map<int, int> acc;
            // first step: calculate diff
            for(int i = 0; i < transactions.size(); i++) {
                int id1 = transactions[i][0];
                int id2 = transactions[i][1];
                int money = transactions[i][2];
                acc[id1] -= money;
                acc[id2] += money;
            }
            
            int res = 0;
            map<int, int> mm;
            for(auto it : acc) {
                if(it.second != 0) {
                    mm[it.second]++;
                }
            }
            
            // divide exactly
            if(mm.size() == 2 && (mm.rbegin()->first % (-mm.begin()->first) == 0 || (-mm.begin()->first) % mm.rbegin()->first == 0)) {
                return max(mm.begin()->second, mm.rbegin()->second);
            }
            
            findAndRemoveOppositePair(mm, res);
            // turn all map values that are larger than 1 to 1
            for(auto it : mm) {
                int firstVal = it.first;
                int secondVal = it.second;
                if(secondVal > 1) {
                    mm[firstVal * secondVal] += 1;
                    mm.erase(firstVal);
                    res += (secondVal-1);
                }
            }
            findAndRemoveOppositePair(mm, res);
            
            while(!mm.empty()) {
                int iter1Key = mm.begin()->first;
                int iter2Key = mm.rbegin()->first;
                int iter1Val = mm.begin()->second;
                int iter2Val = mm.rbegin()->second;
                
                if(abs(iter1Key) > abs(iter2Key)) { // abs(neg) > abs(pos), iter1Key change
                    if(--mm[iter2Key] == 0) {
                        mm.erase(iter2Key);
                    }
                    mm.erase(iter1Key);
                    int newKey = iter1Key + iter2Key;
                    mm[newKey] += iter1Val;
                    res++;
                    if(mm.find(-newKey) != mm.end()) {
                        if(--mm[newKey] == 0) mm.erase(newKey);
                        if(--mm[-newKey] == 0) mm.erase(-newKey);
                        res++;
                    }
                } else {    // abs(pos) > abs(neg), iter2Key change
                    if(--mm[iter1Key] == 0) {
                        mm.erase(iter1Key);
                    }
                    mm.erase(iter2Key);
                    int newKey = iter1Key + iter2Key;
                    mm[newKey] += iter2Val;
                    res++;
                    if(mm.find(-newKey) != mm.end()) {
                        if(--mm[newKey] == 0) mm.erase(newKey);
                        if(--mm[-newKey] == 0) mm.erase(-newKey);
                        res++;
                    }
                }
            }
            return res;
        }
    };
    
    

  • 0

    It does not work with this case:
    [[0,3,9],[1,4,2],[2,5,5],[3,4,6],[4,5,2]]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.