前往
大廳
主題

LeetCode - 1775. Equal Sum Arrays With Minimum Number of Operations 解題心得

Not In My Back Yard | 2024-04-21 12:00:05 | 巴幣 0 | 人氣 36

題目連結:


題目意譯:
你被給定兩個整數陣列 nums1 和 nums2,兩者長度可能不同。陣列中的數值介於 1(含)到 6(含)之間。

在一次操作中,你可以在任一陣列中選擇任一個整數並改變成任意一個介於 1(含)到 6(含)之間的數值。

回傳讓 nums1 中的數值之總和等於 nums2 中的數值之總和最少所需的操作數。如果不可能做到,則回傳 -1。

限制:
1 ≦ nums1.length, nums2.length ≦ 10 ^ 5
1 ≦ nums1[i], nums2[i] ≦ 6



範例測資:
範例 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]。


解題思維:
首先,如果將長度較長的陣列(如果一樣隨便選。設此陣列長度為 L1)中的數字全部換成 1,另一個(設其長度為 L2)則全部換成 6。則可以看到兩者各自總和為 L1 和 6 × L2。而因為我們已經讓長度較長的陣列總和盡可能小、長度較短者總和盡可能大,倘若此時依舊 L1 > 6 × L2,則我們不可能讓兩者總和相同。



接著假設原本總和較大的那一個陣列為 A1(如果總和一樣隨便選),其總和為 S1;而另一者為 A2,其總和為 S2。

掃過一次 A1,統計我們可以有多少「降低量」。例如說,對於數字 5 來說,我們可以變成 1 ~ 4 其中一者,因此最大降低量為 4(即 5 - 1)。因此我們可以把每一種最大降低量統計出來。

另一方面,與上面類似,我們可以對 A2 統計「最大增加量」。

不過我們可以看到「最大增加量為 i」等價於「最大降低量 i」,因為兩者都是為了將 |S1 - S2| 之值變小。因此我們可以將兩種量合併,統一稱「最大變化量」。



令 T = |S1 - S2|。

而由於一次操作中我們是將某個數字變成另一個數字,因此要用盡可能少的操作數讓 T == 0 的話,勢必要從最大變化量大的數字著手。

我們可以先看看有多少個數字(不管是從 A1 還是 A2)最大變化量為 5(假設有 C5 個數字)。此時如果 T ≦ 5 × C5,則代表我們在這個時候可以把 T 變為 0。而次數為 (T + 5 - 1) ÷ 5 取整數(括號裡的「5 - 1」是為了當 T 不是 5 的倍數的時候,次數需要多算一次);反之,如果 T > 5 × C5,則直接將次數加上 C5,並將 T 減去 5 × C5。

對於其他最大變化量 4 ~ 1,重複以上步驟(將 5 出現的地方替換成其他數字即可)直到 T 變為 0。而上述過程中總次數即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作