九章演算法 | Google 面試題 : 最優賬戶結餘

撰文 | JZ

專欄 | 九章演算法

題目描述

一群朋友去度假，有時互相借錢。

例如，愛麗絲為比爾的午餐支付了 10 美元。後來克里斯給愛麗絲 5 美元搭計程車。我們可以假設每筆交易為一個三元組(X,Y,Z)，這意味著第 X 個人借給第 Y 個人 Z 美元。假設 Alice，Bill 和 Chris 是第0，1，2 個人（0，1，2是他們的ID），他們之間的交易可以表示為[ [ 0，1，10 ]，[ 2，0，5 ] ]。

給定一組人之間的交易清單，返回結算所需的最低交易數量。

樣例 1

輸入 [[0,1,10], [2,0,5]]n輸出 2n

樣例解釋

第 2 個人借給第 0 個人 5美元

樣例 2

輸入 [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]n輸出 1n

樣例解釋

第0個人借給第1個人10美元

第1個人借給第2個人5美元

解題思路

1

讀完題我們會發現每個人都有一個借錢的數量和一個還錢的數量(有可能是0)，如果這個人的這兩個值的和為0，那麼他就不需要還錢或者借錢給別人了。

證明：假設此人在借還之和為0的情況下收到 X 的錢，那麼為了收支平衡，必定要把這些錢給另外一個人 Y，那麼這樣不會比X把錢直接給 Y 得到的答案更優。

比如，設三個人的收支情況為[-2,0,2]，那麼第3個人把2轉移到第2個人，再由第2個人轉移到第1個人，需要2次交易，但是第3個人直接轉移給第1個人那麼只需要1次。

2

接下來我們只需要處理所有收支不為0的那些人。我們發現，(在數據合法的情況下)所有人的收支情況的和也是0，那麼我們就來分析一下如何讓答案最小。

對於預處理完收支情況的一個數組[ 2 , 3 , -2 , -3 ](用正數表示收入，負數表示支出)，顯而易見答案是2 （2 → -2 , 3 → -3 ），但是還有一種不是最優的答案3（3 → -2 , 1 → -3 , 2 → -2）。那麼我們就能發現，最優答案是2個子問題([2,-2],[3,-3])的最優解的和。

我們可以用集合枚舉所有的子集，找到每個子集的最優解從而解得總問題的最優解。在這裡我們可以把一個集合的子集定義為一個只有 0,1 的向量，

比如一個有3個元素的集合，他們的子集分別是000(空集),001,010,100,011,110,101,111(全集)，1代表這個子集里有這個元素，0代表這個子集里沒有這個元素。

再利用一個1~n循環來判斷這個子集里有哪些元素，如101代表這個子集里有第1個和第3個元素。

3

接下來我們分析這種解法的時間複雜度，假設去除所有收支平衡以後的人數為n，枚舉子集的時間複雜度為O(2^n),對每個子集進行最優解分析也需要枚舉它的所有子集(這些子集的最優解已經計算完成)，需要的時間複雜度也為O(2^n),最終的時間複雜度為O(4^n)。空間複雜度為O(2^n)。

參考代碼

面試官角度分析

本題難度較大，可能會有多種解法，比如深度優先搜索(需要枚舉所有可能的交易情況)等，效率較低。

假如運用這種預處理+動態規劃或更高效的方法，那麼有 strong hire 的水平，如果能用其他解法(如搜索)解出，則有 hire 的水平。

九章答案鏈接

Optimal account balancing 題解

LintCode 相關題目

k 數和

打劫房屋