[LintCode] Set Union

zhangqh 发布于2019-08-16 12:44 / 3385人阅读

Problem

There is a list composed by sets. If two sets have the same elements, merge them. In the end, there are several sets left.

Example

Given list = [[1,2,3],[3,9,7],[4,5,10]], return 2.

Explanation:
There are 2 sets of [1,2,3,9,7] and [4,5,10] left.
Given list = [[1],[1,2,3],[4],[8,7,4,5]], return 2.

Explanation:
There are 2 sets of [1,2,3] and [4,5,7,8] left.

Solution

public class Solution {
    /**
     * @param sets: Initial set list
     * @return: The final number of sets
     */
    public int setUnion(int[][] sets) {
        int groupNum = sets.length;
        int itemNum = 40000;
        //parent"s length would be the number of groups. 
        //unsure about the number of items, so use 40000 
        int[] parent = new int[groupNum];
        int[] index = new int[itemNum];
    
        for (int i = 0; i < groupNum; i++) {
            parent[i] = i;
        }
        //assign a never-used-in-index value
        Arrays.fill(index, -1);
    
        for (int i = 0; i < sets.length; i++) {
            for (int j : sets[i]) {
                //merge j"s parent with i"s parent first, then update j"s parent
                if (index[j] != -1 && index[j] != i) {
                    merge(parent, i, index[j]);
                }
                index[j] = find(parent, i);
            }
        }
        
        int res = 0;
        for (int i = 0; i < sets.length; i++) {
            if (parent[i] == i) {
                res++;
            }
        }
        return res;
    }
    
    private int find(int[] parent, int a) {
        if (parent[a] == a) {
            return a;
        }
        parent[a] = find(parent, parent[a]);
        return parent[a];
    }
    
    private void merge(int[] parent, int a, int b) {
        int fa = find(parent, a);
        int fb = find(parent, b);
        parent[fa] = fb;
    }
}

云服务器 GPU云服务器 LintCode LintCode134_LRU Union php union

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71606.html

[LeetCode/LintCode] Number of Islands [DFS]

摘要：两个循环遍历整个矩阵，出现则将其周围相邻的全部标记为，用子函数递归标记。注意里每次递归都要判断边界。写一个的，写熟练。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...

Fourierr 2019-08-14 15:15 评论0 收藏0
[LintCode/LeetCode] Set Mismatch

Problem The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetit...

Astrian 2019-08-16 12:45 评论0 收藏0
LintCode547/548_求数组交集不同解法小结

摘要：求数组交集不同解法小结声明文章均为本人技术笔记，转载请注明出处求数组交集要求元素不重复，给出两个数组，求二者交集且元素不重复，查找会超时解法一排序二分查找算法超时主要发生在大数组查找过程，因此采用二分查找提升查找效率，交集用保存实现去重解法 LintCode547/548_求数组交集不同解法小结 [TOC] 声明文章均为本人技术笔记，转载请注明出处：[1] https://segme...

gxyz 2019-08-16 10:34 评论0 收藏0
[LintCode/LeetCode] Intersection of Two Arrays I &

摘要：先想到的是，其实也可以，只是需要在遍历的时候，添加到数组中的数要掉，略微麻烦了一点。在里跑的时候，也要快一点。另一种类似做法的就快的多了。如果是找出所有包括重复的截距呢 Problem Given two arrays, write a function to compute their intersection. Notice Each element in the result m...

enda 2019-08-14 14:03 评论0 收藏0
两数之和问题各变种多解法小结

摘要：两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处两数之和等于题目大意给出未排序数组和指定目标，返回数组中两数之和的组合元素下标要求下标从开始，而且，保证题目中有且只有个可行解解法暴力时间复杂度求解解题思路暴力二重循环求解两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwal...

lentoo 2019-08-16 10:34 评论0 收藏0