给你两个长度可能不等的整数数组 nums1 和 nums2 。两个数组中的所有值都在 1 到 6 之间(包含 1 和 6)。
每次操作中,你可以选择 任意 数组中的任意一个整数,将它变成 1 到 6 之间 任意 的值(包含 1 和 6)。
请你返回使 nums1 中所有数的和与 nums2 中所有数的和相等的最少操作次数。如果无法使两个数组的和相等,请返回 -1 。
示例 1:
输入:nums1 = [1,2,3,4,5,6], nums2 = [1,1,2,2,2,2]
输出:3
解释:你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。
- 将 nums2[0] 变为 6 。 nums1 = [1,2,3,4,5,6], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[5] 变为 1 。 nums1 = [1,2,3,4,5,1], nums2 = [6,1,2,2,2,2] 。
- 将 nums1[2] 变为 2 。 nums1 = [1,2,2,4,5,1], nums2 = [6,1,2,2,2,2] 。
-
贪心最大值变最小值, 最小值变最大值的跨度思想 哈希存储出现的次数
class Solution {
public:
int minOperations(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> hs;
int s1 = 0, s2 = 0;
for(auto x : nums1) s1 += x;
for(auto x : nums2) s2 += x;
int d = s1 - s2;
if(d == 0) return 0;
else if(d > 0){
for(auto x : nums1) hs[x - 1] ++;
for(auto x : nums2) hs[6 - x] ++;
}
else{
for(auto x : nums1) hs[6 - x] ++;
for(auto x : nums2) hs[x - 1] ++;
}
int ans = 0;
if(d < 0) d = -d;
for(int i = 5; i >= 0; i --){
if(d <= 0) return ans;
if(i * hs[i] >= d){
ans += (d + i - 1) / i; // 上去整
d -= i * hs[i];
}
else{
ans += hs[i];
d -= i * hs[i];
}
}
if(d > 0) ans = -1;
return ans;
}
};