主題

LeetCode - 888. Fair Candy Swap 解題心得

Not In My Back Yard | 2021-02-05 00:00:04 | 巴幣 0 | 人氣 20

題目連結:


題目意譯:
Alice 和 Bob 各自有不同大小的糖果棒:A[i] 為 Alice 擁有的第 i 根糖果棒之大小、B[j] 為 Bob 持有的第 j 根糖果棒之大小。

因為他們兩個是好朋友,他們想要交換彼此的一根糖果棒,使得交換完後他們兩者有相同數量的糖果(一個人的糖果數量為其所有糖果棒之大小總和)

回傳一個整數陣列 ans,其中 ans[0] 為 Alice 應交換的糖果棒大小,且 ans[1] 為 Bob 應交換的糖果棒大小。

如果有多個答案,你可以回傳其中的任一個。保證答案存在。

注:
1 ≦ A.length ≦ 10000
1 ≦ B.length ≦ 10000
1 ≦ A[i] ≦ 100000
1 ≦ B[i] ≦ 100000
保證 Alice 和 Bob 擁有不同數量的糖果。
保證至少存在一個答案。



範例測資:
範例 1:
輸入: A = [1,1], B = [2,2]
輸出: [1,2]

範例 2:
輸入: A = [1,2], B = [2,3]
輸出: [1,2]

範例 3:
輸入: A = [2], B = [1,3]
輸出: [2,3]

範例 4:
輸入: A = [1,2,5], B = [2,4]
輸出: [5,4]


解題思維:
將陣列 A 的數字由小排到大(B 也可以,選其中一個即可)。

然後將 A 的所有數字加總得到 TA 、 B 的所有數字加總得到 TB。因為我們需要讓 TA 等於 TB ,且必須交換唯一一次(假設交換的是 A[i] 以及 B[j]),因此我們可以看到
TA - A[i] + B[j] = TB + A[i] - B[j]
調整一下後變成
A[i] = (TA - TB + 2B[j]) ÷ 2
(或是 B[i] = (TB - TA + 2A[j]) ÷ 2,端看想要搜尋哪個陣列)

因此我們掃過陣列 B,對於每個數字 B[j] ,利用二分搜尋法(Binary Search。因為剛剛有排序,所以可以使用,而做法可以參照這題這題)去找陣列 A 是否存在數字之值恰好為 (TA - TB + 2B[j]) ÷ 2。

如果有則此時的 (TA - TB + 2B[j]) ÷ 2 和 B[j] 即是所求。




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

創作回應

更多創作