diff options
author | Jack Sangdahl <[email protected]> | 2024-08-18 21:12:37 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-18 21:12:37 -0600 |
commit | 1d40fa67f4c59b46b14637f2b339f48f69c57df4 (patch) | |
tree | e28574970680352e69f73bc5fa87c7b12648706f | |
parent | c7e6fe204a088a556f0022cbc56fbf5c6839749f (diff) | |
download | leetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.tar.gz leetcode-1d40fa67f4c59b46b14637f2b339f48f69c57df4.zip |
721. accounts merge
-rw-r--r-- | accounts_merge.c | 181 | ||||
-rw-r--r-- | accounts_merge.py | 73 |
2 files changed, 254 insertions, 0 deletions
diff --git a/accounts_merge.c b/accounts_merge.c new file mode 100644 index 0000000..05c49f5 --- /dev/null +++ b/accounts_merge.c @@ -0,0 +1,181 @@ +// 721. Accounts Merge +#include "leetcode.h" + +/* + * given a list of 'accounts' where each element 'accounts[i]' is a list of + * strings, where the first element 'accounts[i][0]' is a name and the rest of + * the elements are emails representing emails of the account. now we would like + * to merge these accounts. two accounts definitely bbelong to the same person + * if there is some common email to bboth accounts. note that even if two + * accounts have the same name, they may belong to different people as people + * could have the same name. a person can have any numbber of accounts initially + * but all of their accounts definitely have the same name. after merging the + * accounts, return the accounts in the following format: the first element of + * each accout is the name, and the rest of the elements are emails in sorted + * order. the accounts themselves can e returned in any order. + */ + +int cmp(const void *a, const void *b) { + char *a1 = *(char **)a, *b1 = *(char **)b; + return strcmp(a1, b1); +} + +int find(int *parent, int i) { + if (parent[i] == i) + return i; + else + return parent[i] = find(parent, parent[i]); +} + +void _union(int *parent, int *rank, int i, int j) { + i = find(parent, i); + j = find(parent, j); + if (i == j) + return; + if (rank[i] > rank[j]) + parent[j] = i; + else { + parent[i] = j; + if (rank[i] == rank[j]) + rank[j]++; + } +} + +int get_idx(const char *email, const char **emails, int emails_size) { + const char **val = bsearch(&email, emails, emails_size, sizeof(char *), cmp); + return (int)(val - emails); +} + +struct res_data { + char ***r; + int *cols; + int size; + int cap; + char **curr; + int curr_size; + int curr_cap; +}; + +void add(struct res_data *r, char *val) { + if (r->curr_cap <= r->curr_size) { + r->curr_cap = (r->curr_cap + 1) * 2; + r->curr = (char **)realloc(r->curr, r->curr_cap * sizeof(char *)); + } + r->curr[r->curr_size++] = val; +} + +void flush(struct res_data *r) { + if (r->cap <= r->size) { + r->cap = (r->cap + 1) * 2; + r->r = (char ***)realloc(r->r, r->cap * sizeof(char **)); + r->cols = (int *)realloc(r->cols, r->cap * sizeof(int)); + } + r->cols[r->size] = r->curr_size; + r->r[r->size++] = r->curr; + r->curr = NULL; + r->curr_cap = r->curr_size = 0; +} + +struct pair { + int idx; + int grp; +}; + +int cmp2(const void *a, const void *b) { + const struct pair *p1 = a, *p2 = b; + if (p1->grp == p2->grp) + return p1->idx - p2->idx; + return p1->grp - p2->grp; +} + +char ***accountsMerge(char ***accounts, int accountsSize, int *accountsColSize, + int *returnSize, int **returnColumnSizes) { + int emails_size, union_find_size, i, j, k, *parent, *rank; + char **emails; + struct pair *p; + struct res_data *r; + memset(&r, 0, sizeof(r)); + for (emails_size = 0, i = 0; i < accountsSize; i++) + for (j = 1; j < accountsColSize[i]; j++) + emails_size++; + emails = (char **)malloc(emails_size * sizeof(char *)); + for (k = 0, i = 0; i < accountsSize; i++) + for (j = 1; j < accountsColSize[i]; j++) + emails[k++] = accounts[i][j]; + qsort(emails, emails_size, sizeof(char *), cmp); + for (i = 0; i < emails_size; ++i) + if (!j || strcmp(emails[j - 1], emails[i])) + emails[j++] = emails[i]; + emails_size = j; + union_find_size = accountsSize + emails_size; + parent = (int *)malloc(union_find_size * sizeof(int)); + rank = (int *)malloc(union_find_size * sizeof(int)); + p = (struct pair *)malloc(union_find_size * sizeof(struct pair)); + for (i = 0; i < union_find_size; i++) { + parent[i] = i; + rank[i] = 0; + } + for (i = 0; i < accountsSize; i++) + for (j = 1; j < accountsColSize[i]; j++) { + // int idx = accountsSize + get_idx(accounts[i][j], (int**)emails, + // emails_size); + int idx = accountsSize + + get_idx(accounts[i][j], (const char **)emails, emails_size); + _union(parent, rank, i, idx); + } + for (i = 0; i < union_find_size; i++) { + struct pair curr = {i, find(parent, i)}; + p[i] = curr; + } + qsort(p, union_find_size, sizeof(struct pair), cmp2); + add(r, accounts[p[0].idx][0]); + for (i = 1; i < union_find_size; i++) + if (p[i].grp != p[i - 1].grp) { + flush(r); + add(r, accounts[p[i].idx][0]); + } else { + int idx = p[i].idx - accountsSize; + if (idx >= 0) + add(r, emails[idx]); + } + flush(r); + *returnSize = r->size; + *returnColumnSizes = r->cols; + free(p), free(parent), free(rank), free(emails); + return r->r; +} + +int main() { + int accountsSize = 4, accountsColSize[] = {3, 3, 2, 2}, returnSize, + *returnColumnSizes; + char ***accounts = malloc(accountsSize * sizeof(char **)); + accounts[0] = malloc(accountsColSize[0] * sizeof(char *)); + accounts[0][0] = "John"; + accounts[0][1] = "[email protected]"; + accounts[0][2] = "[email protected]"; + accounts[1] = malloc(accountsColSize[1] * sizeof(char *)); + accounts[1][0] = "John"; + accounts[1][1] = "[email protected]"; + accounts[1][2] = "[email protected]"; + accounts[2] = malloc(accountsColSize[2] * sizeof(char *)); + accounts[2][0] = "Mary"; + accounts[2][1] = "[email protected]"; + accounts[3] = malloc(accountsColSize[3] * sizeof(char *)); + accounts[3][0] = "John"; + accounts[3][1] = "[email protected]"; + char ***am1 = accountsMerge(accounts, accountsSize, accountsColSize, + &returnSize, &returnColumnSizes); + for (int i = 0; i < returnSize; i++) + for (int j = 0; j < returnColumnSizes[i]; j++) { + printf("\"%s\"", am1[i][j]); + if (j < returnColumnSizes[i] - 1) + printf(", "); + } + for (int i = 0; i < returnSize; i++) + free(am1[i]); + free(am1); + free(returnColumnSizes); + for (int i = 0; i < accountsSize; i++) + free(accounts[i]); + free(accounts); +} diff --git a/accounts_merge.py b/accounts_merge.py new file mode 100644 index 0000000..b2fddb5 --- /dev/null +++ b/accounts_merge.py @@ -0,0 +1,73 @@ +# 721. Accounts Merge +from collections import defaultdict + +""" +given a list of 'accounts' where each element 'accounts[i]' is a list of +strings, where the first element 'accounts[i][0]' is a name and the rest of +the elements are emails representing emails of the account. now we would like +to merge these accounts. two accounts definitely bbelong to the same person +if there is some common email to bboth accounts. note that even if two +accounts have the same name, they may belong to different people as people +could have the same name. a person can have any numbber of accounts initially +but all of their accounts definitely have the same name. after merging the +accounts, return the accounts in the following format: the first element of +each accout is the name, and the rest of the elements are emails in sorted +order. the accounts themselves can e returned in any order. +""" + + +class union_find: + def __init__(self, n): + self.parents = list(range(n)) + + def union(self, child, parent): + self.parents[self.find(child)] = self.find(parent) + + def find(self, x): + if x != self.parents[x]: + self.parents[x] = self.find(self.parents[x]) + return self.parents[x] + + +class Solution(object): + def accountsMerge(self, accounts): + """ + :type accounts: List[List[str]] + :rtype: List[List[str]] + """ + uf = union_find(len(accounts)) + ownership = {} + for i, (_, *emails) in enumerate(accounts): + for email in emails: + if email in ownership: + uf.union(i, ownership[email]) + ownership[email] = i + ans = defaultdict(list) + for email, owner in ownership.items(): + ans[uf.find(owner)].append(email) + return [[accounts[i][0]] + sorted(emails) for i, emails in ans.items()] + + +if __name__ == "__main__": + obj = Solution() + print( + obj.accountsMerge( + accounts=[ + ["John", "[email protected]", "[email protected]"], + ["John", "[email protected]", "[email protected]"], + ["Mary", "[email protected]"], + ["John", "[email protected]"], + ] + ) + ) + print( + obj.accountsMerge( + accounts=[ + ] + ) + ) |