朋友圈裂變算法具體實現(xiàn)之 Quick-Find

• 最近在整理一系列算法，也結合下自己涉及的業(yè)務進行思考。

• 問題產生于現(xiàn)實，實現(xiàn)過程中結合《算法4》。

• 為什么會寫這類文章，是因為最近發(fā)現(xiàn)自己在結構化思維方面有所愛欠缺，對個人職業(yè)發(fā)展很有影響。希望通過書寫這種方式來改變這種模式

• 第二個原因也是最近面試其他程序員過程中，問過類似問題，發(fā)現(xiàn)對方簡單思路都有，但是實際經不起推敲，例如都回答上了這是樹的生成，但是對用什么數(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)通到所有與之相關的黑產。
 *
 * @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,這種模式。
對樹的高度，也就是裂變最大層級，放到下篇文章記錄。