算法之不定期更新（三）（2018-04-24）

darryrzhong 發(fā)布于2019-08-22 16:40 / 3098人閱讀

摘要：實(shí)現(xiàn)這個(gè)想法之后就發(fā)現(xiàn)，時(shí)間復(fù)雜度真的太高了。本期算法小分享就到這里咯剛做完探索里的初級(jí)，還有好多已經(jīng)說爛了的題就不分享了。如果有什么意見或者想法歡迎在評(píng)論區(qū)和我交流

題目

input:


n // 代表無向圖的頂點(diǎn)數(shù) // 從1開始

m // 無向圖的邊數(shù)

arr1 // 各邊的情況，形如[[1, 2], [3, 4],...]（代表頂點(diǎn)0和頂點(diǎn)2相連，頂點(diǎn)3和頂點(diǎn)4相連）

arr2 // 希望求得的連通情況數(shù)組，形如[[1, 3], [1, 4], ...] （代表希望知道頂點(diǎn)1，頂點(diǎn)3的連通情況，頂點(diǎn)1和頂點(diǎn)4的連通情況）

output： num，arr2中可以連通的數(shù)量
示例： input:

n = 3
m = 1
arr1 = [[1, 3]]
arr2 = [[2, 3]]

output: 0

下面是我解決這個(gè)題的時(shí)候的思路

解題思路

這個(gè)題，剛拿到的時(shí)候，我最初的想法是使用無向圖的鄰接矩陣，然后在檢查點(diǎn)的時(shí)候通過廣度優(yōu)先遍歷查看兩個(gè)點(diǎn)是否連通。實(shí)現(xiàn)這個(gè)想法之后就發(fā)現(xiàn)，時(shí)間復(fù)雜度真的太高了。每一次都會(huì)產(chǎn)生許多的無用查詢。

然后我想了另外一個(gè)思路，既然只查詢兩個(gè)點(diǎn)是否連通，那么我們維護(hù)一個(gè)連通集合不就可以了。一開始每一個(gè)孤立的點(diǎn)都是一個(gè)多帶帶的連通集合，形如["1", "2", "3", "4"]，在加上一條邊之后，就是該邊的兩個(gè)頂點(diǎn)所在的連通集合合并成同一個(gè)連通集合，即加上邊[1, 3]后，連通集合變成["13", "2", "4"]。這樣，在查詢的時(shí)候，去尋找頂點(diǎn)B是否在頂點(diǎn)A所處的連通集合里就可以了。于是我寫出了如下的代碼。

代碼

function solution(n, m, arr1, arr2) {
    let hash = new Array(n + 1) // 代表每個(gè)點(diǎn)的所在的連通集合,undefined代表這個(gè)點(diǎn)還不與其他點(diǎn)相連,0位無效
    let map = {} // 保留每個(gè)聯(lián)通集合的點(diǎn)集
    let index = 1 // 下一個(gè)聯(lián)通集合的編號(hào)
    for (let i = 0; i < m; i++) { // 依次添加邊到連通集合里
        let edge = arr1[i]
        let A = edge[0] // 頂點(diǎn)A
        let B = edge[1] // 頂點(diǎn)B
        if (hash[A] === undefined && hash[B] === undefined) { // 這兩個(gè)都是孤立的點(diǎn)，新建一個(gè)連通集合
            hash[A] = index
            hash[B] = index
            map[index++] = [A, B]
        } else if (hash[B] === undefined) { // 點(diǎn)A不是孤立的，點(diǎn)B是孤立的，把B加入A的連通集合里
            hash[B] = hash[A]
            map[hash[A]].push(B)
        } else if (hash[A] === undefined) { // 點(diǎn)B不是孤立的，點(diǎn)A是孤立的，把A加入B的連通集合里
            hash[A] = hash[B]
            map[hash[B]].push(A)
        } else if (hash[A] !== hash[B]) { // A,B均不是孤立的，把B的連通集合,加入A的連通集合里
            B_list = map[hash[B]] // B所在的連通集合的頂點(diǎn)列表
            group = hash[A]
            for (let i = B_list.length - 1; i >= 0; i--) { // 每個(gè)頂點(diǎn)的連通集合修改為A的
                hash[B_list[i]] = group
            }
            map[group] = map[group].concat(map[hash[B]])
            delete map[hash[B]]
        }
    }
    let result = 0 // 連通的數(shù)量
    for (let i = arr2.length - 1; i >= 0; i--) {
        let test = arr2[i]
        let groupA = hash[test[0]]
        let groupB = hash[test[1]]
        if (groupA && groupB && groupA === groupB) {
            result++
        }
    }
    return result
}

也就是，用hash來存放對(duì)應(yīng)的點(diǎn)所在的連通集合，map存放連通集合對(duì)應(yīng)的點(diǎn)。

本期算法小分享就到這里咯（leetcode剛做完探索里的初級(jí)，還有好多已經(jīng)說爛了的題就不分享了。）如果有什么意見或者想法歡迎在評(píng)論區(qū)和我交流