Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

721. Account consolidation

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

Train of thought

  1. withmapTo keep track of all mail boxes and their indexes;
  2. Traverse all the email accounts, determine whether there is the same, if so, link the two accounts;
  3. Go through all the accounts again, pull out all the emails, and put the relevant ones together;
  4. Delete and sort all accounts.

implementation

/ * * *@param {string[][]} accounts
 * @return {string[][]}* /
var accountsMerge = function(accounts) {
    const n = accounts.length;
    const uf = new UnionFind(n);

    // Record every element that occurs
    let map = new Map(a);// Establish a connection
    for (let i = 0; i < n; i++) {
        const list = accounts[i];

        for (let j = 1; j < list.length; j++) {
            // Merge the account if it has appeared before
            if (map.has(list[j])) {
               uf.merge(i, map.get(list[j]));
            } else {
                map.set(list[j], i);
            }
        }
    }

    map = new Map(a);let result = [];
    // Iterate again, and pull out all of the same relationships
    for (let i = 0; i < n; i++) {
        const list = accounts[i];
        const index = uf.find(i);

        // Put the same set together
        if (map.has(index)) {
            const cur = map.get(index)
            result[cur] = result[cur].concat(list.slice(1));
        } else{ map.set(index, result.length); result.push(list); }}// The mailbox is resorted for the third time
    return result.reduce((total, cur) = > {
        const [ name, ...mails  ] = cur;
        total.push([ name ].concat([...new Set(mails)].sort((a, b) = > compareString(a, b))));

        returntotal; } []); };// Compare strings
function compareString(a, b) {
    if(! a || ! b) {return a ? 1 : -1;
    }

    if (a.charCodeAt() - b.charCodeAt() === 0) {
        return compareString(a.slice(1), b.slice(1));
    }

    return a.charCodeAt() - b.charCodeAt()
}

class UnionFind {
  constructor(n) {
    // The parent of each element is itself
    this.parent = new Array(n).fill(0).map((item, index) = > index);
  }

  // Find the parent of the element
  find(index) {
    return this.parent[index] = this.parent[index] === index ? index : this.find(this.parent[index]);
  }

  // Set the parent of index2 to the parent of index1
  merge(index1, index2) {
    this.parent[this.find(index2)] = this.find(index1); }}Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.