溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
中途相遇法，這是一種特殊的算法，大體思路是從兩個不同的方向來解決問題，最終“匯集”到一起?！半p向廣度優(yōu)先搜索”算法就有一點中途相遇的味道。
下面我們通過一道具體的題目，來了解一下這種算法思想的應(yīng)用。
和為0的4個值（4 Value Whose Sum is Zero，ACM/ICPC SWERC 2005，UVa 1152）
給定4個n(1<=n<=400)元素集合A，B，C，D，要求分別從中選取一個元素a,b,c,d，使得a+b+c+d=0。問有多少種選法？
例如，A={-45,-41,-36,26,-32},B={22,-27,53,30,-38,-54},C={42,56,-37,-75,-10,-6},D={-16,30,77,-46,62,45},則有5中選擇法：(-45,-27,42,30),(26,30,-10,-46),(-32,22,56,-46),(-32,30,-75,77),(-32,-54,56,30)。
分析如下：
我們最容易想到的就是寫一個四重循環(huán)枚舉a,b,c,d，看看加起來是否等于0，時間復(fù)雜度為O(n^4),超時。一個稍好的方法就是枚舉a,b,c，則只需要再集合D里面找找是否有元素-a-b-c，如果存在，則方案加1.如果排序后使用二分查找則算法可以適當優(yōu)化。
把剛才的方法加以推廣就可以得到一個更快的算法：首先枚舉a,b，把所有的a+b記錄下來存放在一個有序數(shù)組里，然后枚舉c,d，看看有多少種方法寫成a+b的形式。這里就用到了“中途相遇“的思想。但如果數(shù)據(jù)量較大，以上所述算法也可能會超時。所以，在此處，小編推薦一種更高效的實現(xiàn)方法，就是把a+b放在自己實現(xiàn)的一個哈希表里。這樣，就可以適當程度上優(yōu)化算法。
由于，此博文重在通過一道簡單的例題講述”中途相遇“的思想，重點不在次例題的具體實現(xiàn)算法上。所以，此處沒有寫出具體的實現(xiàn)代碼。小編建議讀者，親自試一下此博文中提到的幾種思想，以便于讓自己對執(zhí)行效率有更加清楚的認識。
由于小編水平有限，歡迎讀者發(fā)現(xiàn)錯誤，并提出錯誤，小編一定積極改正。
免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼
