LeetCode:1202. Smallest String With Swaps交换字符串中的元素(C语言)

素颜马尾好姑娘i 2023-01-04 15:56 116阅读 0赞

**题目描述：**  
给你一个字符串 s，以及该字符串中的一些「索引对」数组 pairs，其中 pairs\[i\] = \[a, b\] 表示字符串中的两个索引（编号从 0 开始）。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后，s 可以变成的按字典序最小的字符串。

示例 1:

输入：s = “dcab”, pairs = \[\[0,3\],\[1,2\]\]  
输出：“bacd”  
解释：  
交换 s\[0\] 和 s\[3\], s = “bcad”  
交换 s\[1\] 和 s\[2\], s = “bacd”

示例 2：

输入：s = “dcab”, pairs = \[\[0,3\],\[1,2\],\[0,2\]\]  
输出：“abcd”  
解释：  
交换 s\[0\] 和 s\[3\], s = “bcad”  
交换 s\[0\] 和 s\[2\], s = “acbd”  
交换 s\[1\] 和 s\[2\], s = “abcd”

示例 3：

输入：s = “cba”, pairs = \[\[0,1\],\[1,2\]\]  
输出：“abc”  
解释：  
交换 s\[0\] 和 s\[1\], s = “bca”  
交换 s\[1\] 和 s\[2\], s = “bac”  
交换 s\[0\] 和 s\[1\], s = “abc”

提示：

1 <= s.length <= 10^5
    0 <= pairs.length <= 10^5
    0 <= pairs[i][0], pairs[i][1] < s.length
    s 中只含有小写英文字母

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/smallest-string-with-swaps  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

struct HashTable { 
        int key;
        int len;
        int* vec;
        UT_hash_handle hh;
    };
    
    int cmp(int* a, int* b) { 
        return *b - *a;
    }
    
    void swap(int* a, int* b) { 
        int tmp = *a;
        *a = *b, *b = tmp;
    }
    
    struct DisjointSetUnion { 
        int *f, *rank;
        int n;
    };
    
    void init(struct DisjointSetUnion* obj, int _n) { 
        obj->n = _n;
        obj->rank = malloc(sizeof(int) * obj->n);
        memset(obj->rank, 0, sizeof(int) * obj->n);
        obj->f = malloc(sizeof(int) * obj->n);
        for (int i = 0; i < obj->n; i++) { 
            obj->f[i] = i;
        }
    }
    
    int find(struct DisjointSetUnion* obj, int x) { 
        return obj->f[x] == x ? x : (obj->f[x] = find(obj, obj->f[x]));
    }
    
    void unionSet(struct DisjointSetUnion* obj, int x, int y) { 
        int fx = find(obj, x), fy = find(obj, y);
        if (fx == fy) { 
            return;
        }
        if (obj->rank[fx] < obj->rank[fy]) { 
            swap(&fx, &fy);
        }
        obj->rank[fx] += obj->rank[fy];
        obj->f[fy] = fx;
    }
    
    char* smallestStringWithSwaps(char* s, int** pairs, int pairsSize, int* pairsColSize) { 
        int n = strlen(s);
        struct DisjointSetUnion* dsu = malloc(sizeof(struct DisjointSetUnion));
        init(dsu, n);
        for (int i = 0; i < pairsSize; i++) { 
            unionSet(dsu, pairs[i][0], pairs[i][1]);
        }
        struct HashTable *mp = NULL, *iter, *tmp;
        for (int i = 0; i < n; i++) { 
            int ikey = find(dsu, i);
            HASH_FIND_INT(mp, &ikey, tmp);
            if (tmp == NULL) { 
                tmp = malloc(sizeof(struct HashTable));
                tmp->key = ikey;
                tmp->len = 1;
                tmp->vec = NULL;
                HASH_ADD_INT(mp, key, tmp);
            } else { 
                tmp->len++;
            }
        }
        HASH_ITER(hh, mp, iter, tmp) { 
            iter->vec = malloc(sizeof(int) * iter->len);
            iter->len = 0;
        }
        for (int i = 0; i < n; i++) { 
            int ikey = find(dsu, i);
            HASH_FIND_INT(mp, &ikey, tmp);
            tmp->vec[tmp->len++] = s[i];
        }
        HASH_ITER(hh, mp, iter, tmp) { 
            qsort(iter->vec, iter->len, sizeof(int), cmp);
        }
    
        for (int i = 0; i < n; i++) { 
            int ikey = find(dsu, i);
            HASH_FIND_INT(mp, &ikey, tmp);
            s[i] = tmp->vec[--tmp->len];
        }
        return s;
    }

**运行结果：**  
!\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20210111090807397.png\#pic\_center

**Notes：**  
参考官方文档：[https://leetcode-cn.com/problems/smallest-string-with-swaps/solution/1202-jiao-huan-zi-fu-chuan-zhong-de-yuan-wgab/][https_leetcode-cn.com_problems_smallest-string-with-swaps_solution_1202-jiao-huan-zi-fu-chuan-zhong-de-yuan-wgab]

[https_leetcode-cn.com_problems_smallest-string-with-swaps_solution_1202-jiao-huan-zi-fu-chuan-zhong-de-yuan-wgab]: https://leetcode-cn.com/problems/smallest-string-with-swaps/solution/1202-jiao-huan-zi-fu-chuan-zhong-de-yuan-wgab/