问题描述 链接到标题

1775.通过最少操作次数使数组的和相等

解题思路 链接到标题

哈希+贪心 链接到标题

本题总体思路为哈希+贪心，用两个数组mp1，mp2记录nums1，nums2中每个数各出现了多少次;

假设nums1的和sum1减去nums2的和sum2的结果为diff，这里假设diff > 0，为了抹平两个数组的和的差距，应该每次减去两个数组中，变化数字引起的数值变化的最大值，并且将变化的数字的计数值减一;

nums1的和小于nums2的和的情况类似。

优化 链接到标题

首先假设sum1 < sum2，否则我们交换nums1和nums2并交换sum1和sum2即可，接下来，必定是nums1缩小，nums2增大，对应diff = sum2 - sum1缩小，diff可以减少1,2,3,4,5各若干次，取决于nums1和nums2中原先各个数的数量，用一个哈希表来记录，最后我们从大到小遍历i = 5, 4, 3, 2, 1.

代码 链接到标题

hash + greedy algorithm 链接到标题 

class Solution {
public:
    int find_min(vector<int> &v) {
        for (int i = 1; i < v.size(); i++) {
            if (v[i] != 0)
                return i;
        }
        return 6;
    }
    int find_max(vector<int> &v) {
        for (int i = v.size() - 1; i >= 1; i--) {
            if (v[i] != 0)
                return i;
        }
        return 1;
    }
    int minOperations(vector<int>& nums1, vector<int>& nums2) {
        int sum1 = 0, sum2 = 0;
        vector<int> mp1(7, 0);
        vector<int> mp2(7, 0);
        if (nums1.size() > 6 * nums2.size() || 6 * nums1.size() < nums2.size())
            return -1;
        for (int i = 0; i < nums1.size(); i++) {
            mp1[nums1[i]]++;
            sum1 += nums1[i];
        }
        for (int i = 0; i < nums2.size(); i++) {
            mp2[nums2[i]]++;
            sum2 += nums2[i];
        }
        int diff = sum1 - sum2;
        int cnt = 0;
        if (diff == 0)
            return cnt;
        else if (diff > 0) {
            // 对nums1, 移动一次最多减少 find_max(mp1) - 1;
            // 对nums2, 移动一次最多增加 6 - find_min(mp2);
            while (diff > 0) {
                cnt++;
                int minus1 = find_max(mp1) - 1;
                int plus2 = 6 - find_min(mp2);
                if (minus1 >= plus2) {
                    diff -= minus1;
                    mp1[find_max(mp1)]--;
                } else {
                    diff -= 6 - find_min(mp2);
                    mp2[find_min(mp2)]--;
                }
            }
            return cnt;
        } else {
            // 对nums1, 移动一次最多增加 6 - find_min(mp1);
            // 对nums2, 移动一次最多减少 find_max(mp2) - 1;
            while (diff < 0) {
                cnt++;
                int minus2 = find_max(mp2) - 1;
                int plus1 = 6 - find_min(mp1);
                if (minus2 >= plus1) {
                    diff += minus2;
                    mp2[find_max(mp2)]--;
                } else {
                    diff += plus1;
                    mp1[find_min(mp1)]--;
                }
            }
            return cnt;                  
        }

    }
};

better code 链接到标题 

class Solution {
  public:
    int minOperations(vector<int> &nums1, vector<int> &nums2) {
        // 先判断不可能相等的情况
        if (nums1.size() > 6 * nums2.size() || nums2.size() > 6 * nums1.size()) {
            return -1;
        }
        // 两个数组的和
        int sum1 = 0, sum2 = 0;
        unordered_map<int, int> mp1;
        for (int &num : nums1) {
            sum1 += num;
        }
        for (int &num : nums2) {
            sum2 += num;
        }
        if (sum1 == sum2) {
            return 0;
        }
        if (sum1 > sum2) {
            vector<int> tmp = nums1;
            int tmp_sum = sum1;
            nums1 = nums2;
            sum1 = sum2;
            nums2 = tmp;
            sum2 = tmp_sum;
        }
        int cnt = 0;
        int diff = sum2 - sum1;
        for (int num : nums1) {
            ++mp1[6 - num];
        }
        for (int num : nums2) {
            ++mp1[num - 1];
        }
        for (int i = 5;; i--) {
            if (diff <= i * mp1[i]) {
                return cnt + (diff + i - 1) / i;
            }
            cnt += mp1[i];
            diff -= i * mp1[i];
        }
        return cnt;
    }
};