时间戳

首页 > 解决方案 > 合并社区并找到最大的社区

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

问题描述

我在 HackerRank 上为这个问题苦苦挣扎。 https://www.hackerrank.com/challenges/friend-circle-queries/problem 我尝试使用自定义链表解决它 - NodeList。它具有三个字段 - 节点优先、节点当前、int 大小。'add' 是一个重载方法。它可以添加一个值或另一个 NodeList。我已将 NodeList 的代码放在注释中，因为它并不重要。

领域：-

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

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

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 但它也有同样的问题，所以我认为问题不在于数据结构。

标签： javaalgorithmlinked-listdisjoint-sets

解决方案

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

我们可以使用不相交的集合数据结构来表示朋友圈的集合。

基本思想是，在每个圈子中，我们分配一个用于表示给定圈子的成员。我们可以称之为根。在圈子中查找多个成员总是委托给存储其大小的根。

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

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

circles所以，对于这个问题，首先我们应该为and定义占位符sizes：

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

对于 中的非 root 成员people，key 是个人 ID，value 是他关注的朋友（可以将他带到 root 的 root 或父级）。根成员在地图中不会有条目。

然后，我们需要一个方法可以让我们到达任何成员的根目录：

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

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

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;
}

推荐阅读