java - 合并社区并找到最大社区的规模

Question

我在 HackerRank 上遇到了这个问题。 https://www.hackerrank.com/challenges/friend-circle-queries/problem我尝试使用自定义链表 - NodeList 来解决它。它具有三个字段 - Node first、Node current、int size。 “add”是一个重载方法。它可以添加一个值或另一个 NodeList。我已将 NodeList 的代码放在注释中，因为它并不重要。

字段:-

static HashMap<Integer, Integer> personToIndex = new HashMap<>();
static int largestCircleSize = 0;
static ArrayList<NodeList> groups = new ArrayList<>();

这是我的业务逻辑方法。当 friend 圈中只有一个人时，我会将另一个人添加到圈子中。当握手的两个人都已经是其他圈子的一部分时，我会合并这些圈子。

static void updateFriendCircles(int friend1, int friend2) {
    int friend1Index, friend2Index;
    NodeList toUpdate;
    friend1Index = personToIndex.getOrDefault(friend1, -1);
    friend2Index = personToIndex.getOrDefault(friend2, -1);
    if (friend1Index != -1) {
        NodeList list = groups.get(friend1Index);
        if (friend2Index != -1) {
            NodeList list2 = groups.get(friend2Index);
            if (list.first == groups.get(friend2Index).first)
                return;
            toUpdate = list.add(list2);
            groups.set(friend2Index, list);
        }
        else {
            toUpdate = list.add(friend2);
            personToIndex.put(friend2, friend1Index);
        }
    }
    else if (friend2Index != -1) {
        toUpdate = groups.get(friend2Index).add(friend1);
        personToIndex.put(friend1, friend2Index);
    }
    else {
        int index = groups.size();
        personToIndex.put(friend1, index);
        personToIndex.put(friend2, index);
        toUpdate = new NodeList(friend1).add(friend2);
        groups.add(toUpdate);
    }
    if (toUpdate.size > largestCircleSize)
        largestCircleSize = toUpdate.size;
}

我也尝试过使用HashSet，但它也有同样的问题，所以我认为问题不在于数据结构。

Answer 1

由于尚不清楚解决方案到底出了什么问题(OP 未指定) - 某些测试用例的答案错误或超时，我将解释如何解决它。

我们可以使用disjoint set表示 friend 圈集合的数据结构。

基本思想是，在每个圈子中，我们分配一个成员来代表给定的圈子。我们可以称其为根。查找圈中的成员数量始终委托(delegate)给存储其大小的根。

每个非根成员都指向他的根成员或指向他可以到达根的成员。将来，当前的根也可能会失去社区的根状态，但随后它将指向新的根，因此始终可以通过链式调用来访问它。

当 2 个圆圈合并时，会从 2 个先前的根成员中选择一个新的根成员。可以将新的尺寸设置到其中，因为之前的根已经包含两个圆的尺寸。但新的根是如何选择的呢？如果圆1的大小不小于圆2的大小，则将其选为新根。

因此，对于这个问题，首先我们应该为圆和大小定义占位符:

Map<Integer, Integer> people;
Map<Integer, Integer> sizes;

对于 people 中的非 root 成员，key 是人员 ID，value 是他关注的 friend (root 或可以让他到达 root 的父级)。根成员在 map 中没有条目。

然后，我们需要一个方法来获取任何成员的根:

int findCommunityRoot(int x) {
    if (people.containsKey(x)) {
        return findCommunityRoot(people.get(x));
    }
    return x;
}

最后，我们需要一种方法来为2给定的 friend 建立社区:

int mergeCommunities(int x, int y) {
    //find a root of x
    x = findCommunityRoot(x);
    //find a root of y
    y = findCommunityRoot(y);

    // one-man circle has a size of 1
    if (!sizes.containsKey(x)) {
        sizes.put(x, 1);
    }
    // one-man circle has a size of 1
    if (!sizes.containsKey(y)) {
        sizes.put(y, 1);
    }

    // friends in the same circle so just return its size
    if (x == y) {
        return sizes.get(x);
    }

    sizeX = sizes.get(x);
    sizeY = sizes.get(y);
    if (sizeX >= sizeY) { 
        people.put(y, x);
        sizes.put(x, sizeY + sizeX); 
        return sizes.get(x);
    } else {
        people.put(x, y);
        sizes.put(y, sizeY + sizeX); 
        return sizes.get(y);
    }
}

因此，我们拥有在每次迭代时保存最大圆尺寸所需的一切:

List<Integer> maxCircle(int[][] queries) {
    List<Integer> maxCircles = new ArrayList<>();

    int maxSize = 1;
    for (int i = 0; i < queries.length; i++) {
        int size = mergeCommunities(queries[i][0], queries[i][1]);
        maxSize = Math.max(maxSize, size);
        maxCircles.add(maxSize);
    }

    return maxCircles;
}