題目
給你兩個長度可能不等的整數陣列 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 <= 105
1 <= nums1[i], nums2[i] <= 6
解題思路分析1、貪心；時間複雜度O(n)，空間複雜度O(1)
func minOperations(nums1 []int, nums2 []int) int { aMin, bMin := len(nums1), len(nums2) aMax, bMax := aMin*6, bMin*6 if aMin > bMax || aMax < bMin { return -1 } a, b := 0, 0 arrA, arrB := [7]int{}, [7]int{} for i := 0; i < len(nums1); i++ { a = a + nums1[i] arrA[nums1[i]]++ } for i := 0; i < len(nums2); i++ { b = b + nums2[i] arrB[nums2[i]]++ } if a == b { return 0 } if b > a { arrA, arrB = arrB, arrA a, b = b, a } arr := make([]int, 0) // 儲存 for i := 1; i < 6; i++ { if arrA[7-i] > arrB[i] { arr = append(arr, arrA[7-i], arrB[i]) } else { arr = append(arr, arrB[i], arrA[7-i]) } } res := 0 total := a - b for i := 0; i < len(arr); i++ { diff := 6 - (i+2)/2 if total-diff*arr[i] > 0 { total = total - diff*arr[i] res = res + arr[i] } else { if total%diff == 0 { res = res + total/diff } else { res = res + total/diff + 1 } return res } } return res}2、貪心；時間複雜度O(n)，空間複雜度O(1)
func minOperations(nums1 []int, nums2 []int) int { aMin, bMin := len(nums1), len(nums2) aMax, bMax := aMin*6, bMin*6 if aMin > bMax || aMax < bMin { return -1 } a, b := 0, 0 arrA, arrB := [7]int{}, [7]int{} for i := 0; i < len(nums1); i++ { a = a + nums1[i] arrA[nums1[i]]++ } for i := 0; i < len(nums2); i++ { b = b + nums2[i] arrB[nums2[i]]++ } if a == b { return 0 } if b > a { arrA, arrB = arrB, arrA a, b = b, a } arr := make([]int, 6) // 儲存 for i := 1; i < 6; i++ { arr[i-1] = arr[i-1] + arrA[7-i] + arrB[i] } res, total := 0, a-b for i := 0; i < len(arr); i++ { diff := 5 - i if total-diff*arr[i] > 0 { total = total - diff*arr[i] res = res + arr[i] } else { if total%diff == 0 { res = res + total/diff } else { res = res + total/diff + 1 } return res } } return res}Medium題目，採用貪心策略