Java 如何找到与同一对象关联的最大对象计数

首先，让我们简要回顾一下任务.

You have a set of mentors, each mentor has a collection of mentees. Some of them might happen also to be mentors and so on.

课堂设计

从类设计的Angular 来看，解决方案非常简单:只需要一个类来描述这种关系——Mentor.每个Mentor应该包含对Mentor个集合(而不是整数ID)的引用.

正如你所描述的，在你的领域模型中，导师和学员之间没有实质性的区别.Mentor指向其他导师——这是一种最简单的建模方法.学员只是一个边缘 case ，一个导师的集合是空的.

您不需要在应用程序中包含不会带来好处的类和功能.

数据 struct

从数据 struct 的Angular 来看，这个问题可以用acyclic disjointed Graph很好地描述.

Acyclic，因为如果我们考虑导师之间的关系，当导师可以间接地指向自己(即导师N有一个受教育者，与另一个被指派的导师同时也是导师N的导师)时，任务变得模棱两可.因此，我假设没有人能成为自己的导师.

我还将这个数据 struct 描述为disjointed，因为这个模型(as well as in real life)中的导师可以形成孤立的小组，在图论中称之为connected components.这意味着可能会有几个导师拥有相同数量的学员，这恰好是最大的.

深度优先搜索

为了找到所有与特定导师相连的顶点(mentors)，我们有一个classic 的遍历算法，称为深度优先搜索(DFS).DFS的核心思想是窥视给定vertex中的一个neighbor，然后依次窥视其neighbors中的一个，依此类推，直到击中不指向其他vertex的vertex(即达到最大深度).然后，在之前访问过的vertices个系统中，每隔neighbors个就应该进行一次.

有两种方法可以实现DFS.

Iterative approach

为此，我们需要stack美元.它将存储之前遇到的vertexes中所有未访问的neighbors.我们将首先探索每branch个列表中neighbors个列表中的最后vertex个，因为它将被放在stack个列表的顶部.然后它将从stack中移除，它的neighbors将被放置在stack中.这个过程在循环中重复，直到stack包含至少一个元素.

对于堆栈来说，性能最好的集合 Select 是ArrayDeque.

因为这种方法需要通过添加和删除vertices来不断修改stack，所以不适合用流IPA实现.

Recursive approach

总体原理与上述相同，但我们不需要提供爆炸性的堆栈.JVM的调用堆栈将用于此目的.

通过这种方法，还可以应用流.因此，我 Select 了递归实现.而且，它的代码可能更容易理解.但请记住，递归有一定的局限性，尤其是在Java中，不适合处理大量数据.

递归

快速回顾递归.

每个递归实现由两部分组成:

• Base case-这代表了一个简单的边缘情况，其结果是事先已知的.对于这个任务，base case是给定的vertex没有neighbors.这意味着这个顶点的menteesCount需要设置为0，因为它没有mentee.base case的返回值是1，因为这vertex又是另一个vertex的有效mentee，其中包含对它的引用.
• Recursive case-解决方案的一部分，其中有recursive calls a，主要逻辑位于其中.

The recursive case可以使用streams实现，并且需要对given vertex中的每neighbor进行递归调用.这些值中的每一个都将构成given vertex个值中的menteesCount个.

该方法返回的值将是menteesCount + 1，因为对于触发该方法调用的vertex，given vertex将是mentee以及它的mentees.

实施

类mentor基本上用作图的顶点.每个顶点都有唯一的id个顶点和相邻顶点的集合.

此外，为了重用通过执行DFS获得的值，我添加了一个field menteesCount，它最初初始化为-1，以便区分没有adjacent vertices的vertices(即menteesCount必须是0)和没有计算值的vertices.每个值将只建立一个值，然后重新使用(another approach will be to utilize a map for that purpose).

方法getTopMentors()对vertices的集合进行迭代，并对每个尚未计算值的vertex调用DFS.此方法返回mentors个列表，其中关联的mentees个列表的数量最多

方法addMentor()采用vertex id，并添加其neighbors(if any)中的id，以便以方便的方式与graph相互作用.

Map mentorById包含graph中添加的每一个vertex，顾名思义，它允许基于vertex id检索它.

public class MentorGraph {
    private Map<Integer, Mentor> mentorById = new HashMap<>();
    
    public void addMentor(int mentorId, int... menteeIds) {
        Mentor mentor = mentorById.computeIfAbsent(mentorId, Mentor::new);
        for (int menteeId: menteeIds) {
            mentor.addMentee(mentorById.computeIfAbsent(menteeId, Mentor::new));
        }
    }
    
    public List<Mentor> getTopMentors() {
        List<Mentor> topMentors = new ArrayList<>();
        for (Mentor mentor: mentorById.values()) {
            if (mentor.getCount() != -1) continue;
            performDFS(mentor);
    
            if (topMentors.isEmpty() || mentor.getCount() == topMentors.get(0).getCount()) {
                topMentors.add(mentor);
        
            } else if (mentor.getCount() > topMentors.get(0).getCount()) {
    
                topMentors.clear();
                topMentors.add(mentor);
            }
        }
        return topMentors;
    }
    
    private int performDFS(Mentor mentor) {
        if (mentor.getCount() == -1 && mentor.getMentees().isEmpty()) { // base case
            mentor.setCount(0);
            return 1;
        }
        
        int menteeCount = // recursive case
            mentor.getMentees().stream()
                .mapToInt(m -> m.getCount() == -1 ? performDFS(m) : m.getCount() + 1)
                .sum();
        
        mentor.setCount(menteeCount);
        return menteeCount + 1;
    }
    
    public static class Mentor {
        private int id;
        private Set<Mentor> mentees = new HashSet<>();
        private int menteesCount = -1;
        
        public Mentor(int id) {
            this.id = id;
        }
        
        public boolean addMentee(Mentor mentee) {
            return mentees.add(mentee);
        }
    
        // getters, setter for menteesCount, equeals/hashCode
    }
}

graph中的100用作demo.

main()-代码对上图进行建模

public static void main(String[] args) {
    MentorGraph graph = new MentorGraph();

    graph.addMentor(1, 3, 4);
    graph.addMentor(2, 5, 6, 7);
    graph.addMentor(3, 8, 9);
    graph.addMentor(4, 10);
    graph.addMentor(5, 11, 12);
    graph.addMentor(6);
    graph.addMentor(7, 13, 14);
    graph.addMentor(8);
    graph.addMentor(9, 16, 17, 18);
    graph.addMentor(10);
    graph.addMentor(11, 18);
    graph.addMentor(12);
    graph.addMentor(13);
    graph.addMentor(14, 19, 20);
    graph.addMentor(15);
    graph.addMentor(16, 21, 22);
    graph.addMentor(17);
    graph.addMentor(18);
    graph.addMentor(19);
    graph.addMentor(20);
    graph.addMentor(21);
    graph.addMentor(22);
    
    graph.getTopMentors()
         .forEach(m -> System.out.printf("mentorId: %d\tmentees: %d\n", m.getId(), m.getCount()));
}

Output

mentorId: 1 mentees: 10
mentorId: 2 mentees: 10