主題
題目連結(jié)：
題目意譯：
你被給定兩個正整數(shù)陣列 nums 和 target，兩者長度相同。
在一次操作中，你可以選擇任兩個相異索引值 i 和 j，其中 0 ≦ i 、 j < nums.length 並且：
將 nums[i] 設為 nums[i] + 2 以及
將 nums[j] 設為 nums[j] - 2。
兩陣列如果每一種元素的出現(xiàn)次數(shù)都一樣，則兩陣列視為「相似的」。
回傳 nums 與 target 變成相似的最少所需操作次數(shù)。測資之生成滿足 nums 永遠都可以與 target 相似。
限制：
n == nums.length == target.length
1 ≦ n ≦ 10 ^ 5
1 ≦ nums[i], target[i] ≦ 10 ^ 6
nums 保證可能與 target 相似。
範例測資：
範例 1：
輸入： nums = [8,12,6], target = [2,14,10]
輸出： 2
解釋： 可以在兩次操作中使 nums 與 target 變?yōu)橄嗨疲?/div>
- 選擇 i = 0 和 j = 2，nums = [10,12,4]。
- 選擇 i = 1 和 j = 2，nums = [10,14,2]。
可以證明 2 為最少所需操作次數(shù)。
範例 2：
輸入： nums = [1,2,5], target = [4,1,3]
輸出： 1
解釋： We can make nums similar to target in one operation:
- 選擇 i = 1 和 j = 2，nums[1,4,3]。
範例 3：
輸入： nums = [1,1,1,1,1], target = [1,1,1,1,1]
輸出： 0
解釋： 陣列 nums 已經(jīng)與 target 相似了。
解題思維：
可以看到題目定義的操作並不會更動到數(shù)字的奇偶性。因此，我們可以把 nums 和 target 兩陣列中各自的奇數(shù)和偶數(shù)分開討論。
而因為題目保證可以讓 nums 變成與 target 相似，因此 nums 中的奇數(shù)之數(shù)量一定會和 target 中的奇數(shù)之數(shù)量相等。兩者的偶數(shù)數(shù)量也是同理。
因此以下我們先討論奇數(shù)的情況：
先將 nums 、 target 兩者各自的奇數(shù)元素由小排到大。並分別以 x1 、 x2 、…… 和 y1 、 y2 、…… 各自指涉 nums 和 target 的數(shù)字。
接著我們可以看到 x1 應與 y1 配對。因為如果存在一個最佳解中有另一數(shù)會先減少（或增加）至 x1 再到 y1，則我們可以直接用 x1 替換其角色即可（也就是說用 x1 去與 y1 配對不會比較差，還可能更好）。
同理，x2 應與 y2 配對、x3 與 y3 配對、……
接著我們再掃過一次每一個配對 (xi, yi)，每當 xi ≧ yi，我們直接忽略這個配對；而當 xi < yi 時，我們便計算出 xi 變成 yi 所需的操作次數(shù)，即 (yi - xi) ÷ 2 次。因為題目的定義，有一數(shù)增加必有另一數(shù)減少。那我們剛剛算出的操作次數(shù)中該減少的數(shù)字（們）應為何？
答案是，我們不需要知道。正因為題目保證 nums 可以變得與 target 相似，代表著我們此時的數(shù)字增加量必定可以對應到某些數(shù)字的減少量之總和。而這也是為何我們可以直接忽略掉 xi ≧ yi 的情況，因為我們不需要額外算這些配對的所需次數(shù)，xi < yi 已經(jīng)做完了。
以上，我們便可以得到所有 nums 中的奇數(shù)與 target 中的奇數(shù)變?yōu)橄嗨频淖钌偎璐螖?shù)。而偶數(shù)也是同理。最後將奇數(shù)的結(jié)果與偶數(shù)的結(jié)果加總即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
