“This is the 17th day of my participation in the First Challenge 2022.

Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

Given a list accounts, each element accounts[I] is a list of strings, where the first element accounts[I][0] is the name, and the remaining elements are emails representing the email address of the account.

Now, we want to consolidate these accounts. If two accounts have some email addresses in common, they must belong to the same person. Note that even if two accounts have the same name, they may belong to different people because people may have the same name. A person can initially have any number of accounts, but all of them have the same name.

After merging the accounts, the accounts are returned in the following format: the first element of each account is the name, and the remaining elements are the mailbox address in ASCII character order. The accounts themselves can be returned in any order.

Example 1:

Input:  accounts = [["John", "[email protected]", "[email protected]"], ["John", "[email protected]"], ["John", "[email protected]", "[email protected]"], ["Mary", "[email protected]"]  [["John", '[email protected]', '[email protected]', '[email protected]'], ["John", "[email protected]"], ["Mary", "[email protected]"] Explanation: The first John and the third John are the same person because they share the email address "[email protected]". The second John and Mary are different people because their email addresses are not used by other accounts. These lists can be returned in any order, such as answers [['Mary', '[email protected]'], ['John', '[email protected]'], ['John', '[email protected]', '[email protected]', '[email protected]']] are also correct.Copy the code

Example 2:

Input:  accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","Ethan5@m. co","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]"," [email protected] "]] output:  [["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","Hanzo0@m .co","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]", "[email protected]"]]Copy the code

Tip:

  • 1 <= accounts.length <= 1000
  • 2 <= accounts[i].length <= 10
  • 1 <= accounts[i][j].length <= 30
  • accounts[i][0]Consists of English letters
  • accounts[i][j] (for j > 0)Is a valid email address

Their thinking

In this case, we use Map and search set.

  • First of all, we take out all non-duplicate mailboxes and use two map structures to store the marks of each mailbox and corresponding user names respectively.

  • Use the number of mailboxes to initialize and look up the set

  • Through the mailbox in the account, make merge mark

  • Group, sort, and add user names to labeled mailboxes

  • The output

The problem solving code

var accountsMerge = function(accounts) {
    const nameMap = new Map(a)const indexMap = new Map(a)let count = 0
    accounts.forEach(account= >{
        for(let i =1; i<account.length; i++){// only loop mailboxes
            const email = account[i]
            if(! indexMap.has(email)){// Operate on non-duplicate mailboxes
                nameMap.set(email,account[0]) // Email -> user name
                indexMap.set(email,count++) // mailbox -> unique index corresponding}}})const union = new UnionFind(count)  // Initialize and look up the set
    accounts.forEach(account= >{
        const firstIndex = indexMap.get(account[1])
        for(let i =2; i<account.length; i++){// Try merging each mailbox of the account
            const secondIndex = indexMap.get(account[i])
            union.merge(firstIndex,secondIndex)
        }
    })
    // The mailbox of the same account will be marked as the same

    const indexToEmails = new Map(a); [...indexMap.keys()].forEach(key= >{ // key -> mailbox
        const index =  union.find(indexMap.get(key))  // get the index corresponding to the mailbox and check the mark in the set
        const account = indexToEmails.get(index)||[] // Group mailboxes with the tag in the look-up set
        account.push(key)
        indexToEmails.set(index,account)
    })
    const result = [];
     [...indexToEmails.keys()].forEach(key= >{ // select * from key
        const emails = indexToEmails.get(key).sort() // Get the mailbox and sort it
        const name = nameMap.get(emails[0])  // Obtain the user name corresponding to the mailbox
        result.push([name, ...emails]);  // Assemble data
    })
    return result  // Output the result
};  

/ / and set
class UnionFind {
    constructor(len){
        this.parents = new Array(len).fill(0).map((v,i) = >i)
        this.rank =  new Array(len).fill(0)}find(i){ // Find the root node
        if(this.parents[i] == i ) return i
        return this.find(this.parents[i])
    }
    connect(a,b){ // Check whether it is connected
        return this.find(a) == this.find(b)
    }
    merge(a,b){ / / merge
        if(this.connect(a,b)) return
        const fa = this.find(a)
        const fb = this.find(b)
        if(this.rank[fa]>this.rank[fb]){
            this.parents[fb] = fa
        }else{
            this.parents[fa] = fb
            if(this.rank[fa]==this.rank[fb] ){
                this.rank[fb]++
            }
        }
    }
}
Copy the code

This question really thought for a long time, just sort out this article, I hope to have a little help to you.

If you have any questions or suggestions, please leave a comment!