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

Question

我有一个 Mentor class，其中每个导师都有一个 ID，还有一个 ArrayList 的受训者 ID，如下所示：

public class Mentor {
    
    int mentorId;
    ArrayList<Integer> mentees = new ArrayList<>();

    public Mentor(int mentorId, ArrayList<Integer> mentees) {
        this.mentorId = mentorId;
        this.mentees = mentees ;
    }
}

问题是一些学员也可以是导师。

我想以某种方式获得 count 的所有 mentees 关联到顶级导师以及顶级导师手下有多少导师。

所以，基本上，如果导师有一个导师，他也是导师，那么这位导师的学员也关联到顶级导师。

所以，我的想法是遍历 mentee-list 并查看是否有任何 id 匹配 ID of Mentor。如果为真，则将此导师的受训者列表添加到列表中并再次循环，但这将无法动态工作。

我的主要 class 看起来像这样：

    ArrayList<Mentor> mentors = new ArrayList<>();
    ArrayList<Integer> mentees = new ArrayList<>();
    ArrayList<Integer> mentees2 = new ArrayList<>();

    mentees.add(2);
    mentees.add(3);
    mentees2.add(4);
    mentees2.add(5);

    //[1,{2,3}]
    mentors.add(new Mentor(1, mentees));
    //[2,{4,5}]
    mentors.add(new Mentor(2, mentees2));
    int mentorCount = 0;
    int menteeCount = 0;
    for (Mentor mentor : mentors) {

        for (Integer mentee : mentees) {
            mentorCount++;
            if (mentee == mentor.mentorId){
                mentorCount++;
                //add each mentee to arraylist and start the process again, but is there an easier way to do this.
            }
        }
    }

我想知道是否有解决这个问题的方法，也许使用 streams?

Answer 1

您应该执行 depth-first 或 breadth-first 搜索 (*):

维护一个 Set<Integer> 包含所有你已经见过的人。
维护一个队列（例如 ArrayDeque），您要检查的人。
将第一个人（或任意数量的人）放入此队列。
然后，当队列不为空时：
- 排队的下一个人
- 如果您已经看过它们，请转到队列中的下一项
- 如果你还没有见过他们，把这个人放到见过的集合中；将他们所有的学员加入队列

就是这样。最后的人数就是看到的集合的大小

(*) 您是进行 depth-first 还是 breadth-first 搜索取决于您将学员添加到队列的哪一端：将他们添加到您从结果中删除他们的同一端 depth-first 搜索；将它们添加到另一端会导致 breadth-first 搜索。如果您不在乎哪个，请选择其中一个。

Answer 2

我建议使用良好的面向对象设计，你不应该只使用整数 id，因为在这种情况下你可以简单地创建一个 ArrayList of Person 对象，其中 Mentees 和 Mentors 继承自 Person。然后你可以检查一个人是否是 Mentee 与 Mentor 的实例：

for (Person p : people) {
    if (p instanceof Mentor)
    {
        // Mentor logic
    }
    if (p instanceof Mentee)
    {
        // Mentee Logic
    }
}

Answer 3

首先，简单回顾一下任务。

你有一组导师，每个导师都有一组学员。他们中的一些人可能恰好也是导师等等。

Class设计

从class设计的角度来看，解决方案很简单：只需要一个class来描述这个关系——Mentor。每个 Mentor 都应该包含对 Mentor 集合的引用（不是整数 ID）。

正如您所描述的，在您的领域模型中，导师和受训者之间没有实质性区别。导师指向其他导师——这是一种最简单的建模方式。 Mentee 只是一个边缘案例，一个导师集合为空的导师。

您不需要在您的应用程序中包含 class 不会带来好处的内容和功能。

数据结构

从数据结构的角度来看，这个问题可以用无环不相交图.

很好的描述

非循环因为如果我们考虑导师之间的关系，当导师可以间接指向他们自己时（即导师N有一个被指导者，用in tern指向另一个学员恰好也是导师的导师 N) 任务变得模棱两可。因此，我假设没有人可以成为自己的导师。

我还将此数据结构描述为脱节，因为此模型（以及现实生活中）中的导师可以形成孤立的群体，在图论中称为 连通分量 。这意味着可能有几个导师拥有相同数量的受训者，这恰好是最大的。

深度优先搜索

为了找到与特定导师相连的所有顶点（导师），我们有一个classic遍历算法，称为深度优先搜索（DFS）。 DFS 的核心思想是查看给定 vertex 的单个 neighbor，然后依次查看它的 neighbor =180=] 等等，直到命中 vertex 不指向另一个 vertex （即达到最大深度）。然后它应该与之前访问过的顶点 .

的所有其他邻居一起完成

有两种实现 DFS 的方法。

迭代方法

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

堆栈集合的最佳性能选择是 ArrayDeque。

因为这种方法需要通过添加和删除顶点来不断修改堆栈，所以不适合用Stream实现国际音标

递归方法

总体原理和上面介绍的一样，只是我们不需要爆提供栈。 JVM 的调用堆栈将用于该目的。

通过这种方法，还有一些应用流的空间。出于这个原因，我选择了递归实现。此外，它的代码可能更容易理解一些。但要记住，递归有一定的局限性，尤其是在Java，不适合处理大量数据。

递归

递归快速回顾。

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

基本案例 - 代表一个简单的 edge-case，其结果是预先知道的。对于这个任务，base case 是给定的 vertex 没有 neighbors。这意味着这个顶点的 menteesCount 需要设置为 0 因为它没有 mentee。 基本案例的return值为1，因为这个顶点反过来是一个有效的mentee 另一个 vertex 持有对它的引用。
递归案例 - 解决方案的一部分，其中 递归调用 已完成并且主要逻辑所在。

递归情况可以使用streams实现，并且需要为每个neighbor[=180递归调用=] 给定的顶点。这些值中的每一个都将对给定顶点的menteesCount做出贡献。

由该方法编辑的值 return 将e menteesCount + 1 因为对于触发此方法调用的 vertex，given vertex 将是 mentee 及其学员.

实施

Class 导师基本上充当了图的一个顶点。每个顶点都有一个唯一的 id 和相邻顶点的集合。

此外，为了重用通过执行 DFS 获得的值，我添加了一个字段 menteesCount ，它最初被初始化为 -1 以便区分没有 相邻顶点 的顶点（即 menteesCount 必须是 0）和 vertices 未计算哪个值。每个值都将只建立一个值，然后重复使用（另一种方法是为此目的使用地图）。

方法getTopMentors()遍历顶点的集合并为每个尚未计算值的顶点调用DFS .此方法 return 是 指导者 的列表，其中关联的 指导者
数量最多
方法addMentor()采用顶点id和它的邻居[=180]的id =]（if any）已添加，以便以方便的方式与 graph 交互。

Map mentorById 包含添加到 graph 中的每个 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 } }

用作演示的示例 =180=].

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

输出

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

Answer 4

按照的建议使用 Person 和 Mentor 以及 Mentee 子类，将 mentees 定义为 Person 的列表和您想要的信息变得很容易获得：

import java.util.*;
import java.util.stream.Stream;

public class Main{

    public static void main(String[] args)  {
        ArrayList<Person> mentees = new ArrayList<>();

        mentees.add(new Mentee(11));
        mentees.add(new Mentee(12));
        mentees.add(new Mentor(2, new ArrayList<>()));
        mentees.add(new Mentee(13));
        mentees.add(new Mentee(14));
        mentees.add(new Mentor(3, new ArrayList<>()));
        mentees.add(new Mentor(4, new ArrayList<>()));
        mentees.add(new Mentor(5, new ArrayList<>()));

        Mentor mentor = new Mentor(1, mentees);

        System.out.println(mentor.menteesCount());
        System.out.println(mentor.mentorsInMentees().count());
    }
}

interface Person {
    int getId();
}

class Mentor implements Person{

    private final int mentorId;
    private List<Person> mentees = new ArrayList<>();

    public Mentor(int id, ArrayList<Person> mentees) {
        mentorId = id;
        this.mentees = mentees ;
    }

    @Override
    public int getId() {
        return mentorId;
    }

    public List<Person> getMentees() {
        return mentees;
    }

    public int menteesCount() {
        return mentees.size();
    }

    public Stream<Person> mentorsInMentees(){
        return mentees.stream().filter(m -> (m instanceof Mentor));
    }
}

class Mentee implements Person{

    private final int menteeId;

    public Mentee(int id) {
        menteeId = id;
    }

    @Override
    public int getId() {
        return menteeId;
    }
}

在线测试here

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

How to find the largest Count of Objects assosiated with the same Object

java

algorithm

graph

arraylist

java-stream

Class设计

数据结构

深度优先搜索

递归

实施