[LintCode] Set Union

zhangqh 發布于2019-08-16 12:44 / 3409人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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