朋友圈裂變算法具體實現(xiàn)之 Quick-Find
最近在整理一系列算法吨娜，也結合下自己涉及的業(yè)務進行思考问拘。
問題產(chǎn)生于現(xiàn)實夯接，實現(xiàn)過程中結合《算法4》焕济。
為什么會寫這類文章，是因為最近發(fā)現(xiàn)自己在結構化思維方面有所愛欠缺盔几，對個人職業(yè)發(fā)展很有影響晴弃。希望通過書寫這種方式來改變這種模式
第二個原因也是最近面試其他程序員過程中，問過類似問題逊拍，發(fā)現(xiàn)對方簡單思路都有上鞠，但是實際經(jīng)不起推敲，例如都回答上了這是樹的生成芯丧，但是對用什么數(shù)據(jù)結構都沒有整體思路芍阎。
本系列是用代碼來書寫，注釋中有實現(xiàn)思路缨恒。
Go版本算法谴咸，只做驗證不做說明
思路
1：算法設計條條大路轮听。但是好的數(shù)據(jù)結構永遠是第一步。</br>
2：問題描述
- 輸入一列數(shù)列岭佳，其中每個整數(shù)都可以表示一個某種類型的對象血巍。
- 假設P、Q代表兩個對象珊随，在實際業(yè)務中述寡，可以代表兩個對象的ID。
如果相連：</br> - 1：自反性（自己與自己鏈接叶洞，不需要實現(xiàn)）
- 2：對稱（也不需要特意聲明和實現(xiàn)）
- 3：傳遞（Q-P Q-R 那么P-R）union主要實現(xiàn)是這個認證鲫凶。
java版本
/**
* 輸入一列數(shù)列，其中每個整數(shù)都可以表示一個某種類型的對象衩辟。
* 假設P螟炫、Q代表兩個對象，在實際業(yè)務中艺晴，可以代表兩個對象的ID不恭。
* 如果相連：
* 1：自反性（自己與自己鏈接，不需要實現(xiàn)）
* 2：對稱（也不需要特意聲明和實現(xiàn)）
* 3：傳遞（Q-P Q-R 那么P-R）union主要實現(xiàn)是這個認證财饥。
* <p>
* 場景：網(wǎng)絡
* 例如社交網(wǎng)路朋友關系等
* 結合我們現(xiàn)在社交電商，可以利用這個算法分析有多少個裂變點折晦，也可以計算某一個人所有相關的裂變钥星，
* 如果判斷某一客戶反復刷單，就能聯(lián)通到所有與之相關的黑產(chǎn)满着。
*
* @author 馬曉超
* @date 20180422
*/
public class QuickFind {
//數(shù)據(jù)結構
private int count;
private int[] uf;
public int size() {
return uf.length;
}
public int[] getUf() {
return uf;
}
//行為抽象
//初始化N個節(jié)點
public QuickFind(int N) {
//初始分量數(shù)組谦炒，N只是模擬1到N的對象，如果用現(xiàn)實中的代替风喇，就是【ID】=地址這種模式宁改。
uf = new int[N];
for (int i = 0; i < N; i++) {
uf[i] = i;
}
count = N;
}
//Find找到這個P所在節(jié)點的標記（比如p是人標記就是p的地址）
public int find(int p) {
validate(p);
return uf[p];
}
//判斷p,q是否相連
public boolean connected(int p, int q) {
validate(p);
validate(q);
return find(p) == find(q);
}
//聯(lián)通分量的數(shù)量，如果用關系網(wǎng)絡來解釋魂莫，就是有多少個獨立的網(wǎng)絡还蹲。
public int count() {
return count;
}
private void validate(int p) {
int n = uf.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
//核心算法union
//
/**
* p 鏈接 q
* p=3,q=4
* a,b,c,[p],q,e,f,g,h,j
* 連接前 0,1,2,3,4,5,6,7,8,9
* 連接后 0,1,2,4,4,5,6,7,8,9
* <p>
* q，r=2
* 連接前 0,1,2,4,4,5,6,7,8,9
* 連接后 0,1,2,2,2,5,6,7,8,9
*
* @param p
* @param q
*/
public void union(int p, int q) {
if(connected(p,q)){
return;
}
//p address
int pa = find(p);
//q address
int qa = find(q);
//鏈接一條耙考，就從總數(shù)減一條
count--;
//1:循環(huán)所有的結點谜喊，找出pa的值從注釋里示例上就是找出id=3的標記
//2:把pa都編程qa代表他們連到了一起
for (int i = 0; i < uf.length; i++) {
if (uf[i] == pa) {
uf[i] = qa;
}
}
}
public static void main(String[] args) {
//模擬1個節(jié)點
QuickFind quickFind = new QuickFind(10);
//3-4鏈接
quickFind.union(3, 4);
//4-2鏈接
quickFind.union(4, 2);
//驗證
// 總得count應該等于 10-2
if (quickFind.count() != 8) {
throw new RuntimeException("鏈接分量不正確");
}
//地址2 應該有三個
int i = 0;
for (int j = 0; j < quickFind.size(); j++) {
if (quickFind.getUf()[j] == 2) {
i++;
}
}
if (i != 3) {
throw new RuntimeException("節(jié)點數(shù)不正確");
}
quickFind.union(8, 3);
quickFind.union(9, 0);
//view Uf
for (int j = 0; j < quickFind.size(); j++) {
System.out.println(quickFind.getUf()[j]);
}
}
}
Go版本
package main
import "fmt"
type QF struct {
Uf []int
Count int
}
//
func (qf *QF) Union(p, q int) {
if qf.connected(p,q) {
return
}
pa := qf.Uf[p]
qa := qf.Uf[q]
for i := 0; i < len(qf.Uf); i++ {
if qf.Uf[i] == pa {
qf.Uf[i] = qa
}
}
qf.Count--
}
func (qf *QF) Init(n int) {
qf.Uf = make([]int, n)
for i := 0; i < n; i++ {
qf.Uf[i] = i
}
qf.Count = n
}
func (qf QF) connected(p, q int) bool {
return qf.Uf[p] == qf.Uf[q]
}
func main() {
qf := new(QF)
qf.Init(10)
qf.Union(3, 4)
qf.Union(4, 9)
fmt.Println(qf.Uf)
fmt.Println(qf.Count)
}
復雜度
O(N）
缺陷
數(shù)據(jù)規(guī)模有限制。實際業(yè)務可以適當修改倦始，例如：[uid]=uid,這種模式斗遏。
對樹的高度，也就是裂變最大層級鞋邑，放到下篇文章記錄诵次。
