【2022-12-07每日一题】1775. 通过最少操作次数使数组的和相等[Medium]
2022-12-07
4分钟阅读时长
2022-12-07每日一题：1775. 通过最少操作次数使数组的和相等
难度：Medium
标签：贪心 、 数组 、 哈希表 、 计数
给你两个长度可能不等的整数数组 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] 。
示例 2：
输入：nums1 = [1,1,1,1,1,1,1], nums2 = [6] 输出：-1 解释：没有办法减少 nums1 的和或者增加 nums2 的和使二者相等。
示例 3：
输入：nums1 = [6,6], nums2 = [1] 输出：3 解释：你可以通过 3 次操作使 nums1 中所有数的和与 nums2 中所有数的和相等。以下数组下标都从 0 开始。 - 将 nums1[0] 变为 2 。 nums1 = [2,6], nums2 = [1] 。 - 将 nums1[1] 变为 2 。 nums1 = [2,2], nums2 = [1] 。 - 将 nums2[0] 变为 4 。 nums1 = [2,2], nums2 = [4] 。
提示：
1 <= nums1.length, nums2.length <= 1051 <= nums1[i], nums2[i] <= 6
方法一：贪心 + 哈希表【官方】
func minOperations(nums1 []int, nums2 []int) int {
m, n := len(nums1), len(nums2)
if 6*m < n || 6*n < m {
return -1
}
var cnt1, cnt2 [7]int
diff := 0
for _, x := range nums1 {
cnt1[x]++
diff += x
}
for _, x := range nums2 {
cnt2[x]++
diff -= x
}
if diff == 0 {
return 0
}
if diff > 0 { // nums1 > nums2
return help(cnt2, cnt1, diff)
}
return help(cnt1, cnt2, -diff)
}
func help(h1 [7]int, h2 [7]int, diff int) (res int) {
h := [7]int{}
for i := 1; i < 7; i++ {
h[6-i] += h1[i]
h[i-1] += h2[i]
}
for i := 5; i > 0 && diff > 0; i-- {
t := min((diff+i-1)/i, h[i])
res += t
diff -= t * i
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
复杂度分析
时间复杂度：O(n+m)，其中 n，m 分别为数组 nums1，nums2的长度。
空间复杂度：O(C)，其中 C 为数组 nums1，nums2中元素值的取值空间，主要为用数组来模拟「哈希表」的空间开销。
方法二：灵茶山艾府
func minOperations(nums1, nums2 []int) (ans int) {
if 6*len(nums1) < len(nums2) || 6*len(nums2) < len(nums1) {
return -1 // 优化
}
d := 0 // 数组元素和的差，我们要让这个差变为 0
for _, x := range nums2 { // nums2 在前
d += x
}
for _, x := range nums1 { // nums1 在后
d -= x
}
if d < 0 {
d = -d
// 统一让 nums1 的数变大，nums2 的数变小
nums1, nums2 = nums2, nums1
}
cnt := [6]int{} // 统计每个数的最大变化量
for _, x := range nums1 {
cnt[6-x]++ // nums1 的变成 6
}
for _, x := range nums2 {
cnt[x-1]++ // nums2 的变成 1
}
// 从大到小枚举最大变化量 5 4 3 2 1
for i := 5; ; i++ {
if cnt[i]*i >= d { // 可以让 d 变为 0
return ans + (d+i-1)/i
}
ans += cnt[i] // 需要所有最大变化量为 i 的数
d -= cnt[i] * i
}
}
复杂度分析
时间复杂度：O(n+m)，其中 n 为 nums1的长度，m 为 nums2的长度。
空间复杂度：O(C)。本题 C=6。
方法三：ylb
func minOperations(nums1, nums2 []int) (ans int) {
s1, s2 := sum(nums1), sum(nums2)
if s1 == s2 {
return 0
}
// 处理成 nums1 小于 nums2
if s1 > s2 {
nums1, nums2 = nums2, nums1
s1, s2 = s2, s1
}
d := s2 - s1
cnt := [6]int{}
for _, x := range nums1 {
cnt[6-x]++ // x 变大
}
for _, x := range nums2 {
cnt[x-1]++ // x 变小
}
for i := 5; i > 0; i-- {
for cnt[i] > 0 && d > 0 {
d -= i
cnt[i]--
ans++
}
}
if d <= 0 {
return ans
}
return -1
}
func sum(nums []int) (s int) {
for _, x := range nums {
s += x
}
return s
}
复杂度分析
时间复杂度：O(n+m)，其中 n 为 nums1的长度，m 为 nums2的长度。
空间复杂度：O(C)。本题 C=6。