LC.P1775[通过最少操作次数使数组的和相等]

方法一：贪心+计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (6 * m < n || 6 * n < m) return -1;
        int d = 0;
        for (int x : nums2) d += x;
        for (int x : nums1) d -= x;
        // 交换，统一让 nums1 的数变大，nums2 的数变小
        if (d < 0) {
            d = -d;
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int[] cnt = new int[6];
        for (int x : nums1) ++cnt[6 - x];
        for (int x : nums2) ++cnt[x - 1];
        int ans = 0;
        for (int i = 5; i > 0; --i) {
            while (cnt[i] > 0 && d > 0) {
                d -= i;
                --cnt[i];
                ++ans;
            }
        }
        return d <= 0 ? ans : -1;
    }
}
  • 时间复杂度：$O(m + n)$
  • 空间复杂度：$O(C)$，$C = 6$