代码之家 › 专栏 › 技术社区 › flash

从圈里找一小群朋友?

hashmap data-structures algorithm java

flash · 技术社区 · 6 年前

我正在解决以下问题:

在一个有人的房间里,我们将定义两个人是朋友,如果他们是直接或间接的朋友。如果A是B的朋友,而B是一个和C的朋友,那么A也是C的朋友。一群朋友是一组任何两个人是朋友的人。鉴于直接成为朋友的人的列表,找到最小的一组朋友们…

例子: 输入:

1<->6 
2<->7
3<->8
4<->9
2<->6
3<->5

组:

1-6-2-7
3-8-5
4-9

最小组的人数是2,即4-9,所以我们应该返回2。

我想出了下面的代码,但我不知道如何使用它 holder 现在映射以获得所需的输出。我有点困惑。解决这个问题的最佳方法是什么?

  private static int findGroups(final List<List<Integer>> inputs) {
    if (inputs == null || inputs.isEmpty()) {
      return 0;
    }
    int count = Integer.MAX_VALUE;

    Map<Integer, List<Integer>> holder = new HashMap<>();
    for (List<Integer> input : inputs) {
      // storing it in bidirectional way in the map
      List<Integer> l =
          holder.containsKey(input.get(0)) ? holder.get(input.get(0)) : new ArrayList<Integer>();
      l.add(input.get(1));
      holder.put(input.get(0), l);

      List<Integer> l1 =
          holder.containsKey(input.get(1)) ? holder.get(input.get(1)) : new ArrayList<Integer>();
      l1.add(input.get(0));
      holder.put(input.get(1), l1);
    }
    System.out.println(holder);

    // use holder map to get the smaller group here?

    return count;
  }

看起来我需要在这里使用递归来获得较小的组?

2 回复 | 直到 6 年前

ruakh 6 年前

有没有更好的方法来解决这个问题?

更好的方法是使用 disjoint-set data structure :

首先,将“朋友组”计算为不相交的集合数据结构:
- 初始化一个不相交的集合数据结构,其中集合的元素将是房间中的人员。
- 为每个人磷房间里:
  - 呼叫 马克塞特 ( 磷 )初始化仅包含此人的“朋友组”。
- 为每一个直接的友谊磷 _一艾斯磷 _二 :
  - 呼叫联合 ( 磷 _一 , 磷 _二 )统一包含磷 _一与包含磷 _二 .
接下来,计算“朋友组”的大小作为地图:
- 初始化一个地图,其中键将是房间中的一些人(即他们各自的“朋友组”的代表),值将是数字(即各种“朋友组”的大小)。
- 为每个人磷 _一房间里:
  - 呼叫发现 ( 磷 _一 )找到代表磷 _二在那个人的“朋友组”中。
  - 如果映射尚未包含键的值磷 _二 ,插入该键的值0。
  - 增加键的值磷 _二 .
最后,计算结果:
- 将结果初始化为较大的值,例如房间中的人数。
- 对于地图中的每个值(=一个“朋友组”的大小):
  - 如果该值小于结果,则将结果设置为等于该值。
- 返回结果。

顺便说一下,你正在执行的操作的技术名称是 transitive closure “是朋友”关系是“直接是朋友”关系的传递闭包。(然而,维基百科文章中描述的算法并不适合你的问题,因为它们没有利用你的关系 symmetric )

parsecer 6 年前

这是一些代码,我出于好奇写下了你的问题。我对图形不太了解,但它使用递归,就像您所要求的那样。

基本上,你通过输入,为每个人,你创建一个 ArrayList<Integer> . 在这个数组中,是那个人的直接朋友。例如,对于 1: {6}, for 2: {7, 6}, for 3: {8, 5} . 然后,得到 全部的 第二个人的朋友,你创造了一个整体 数组列表<integer> 将第7和第6个人的数组组合在一起(不包括重复的数组)。因此,递归可以用函数 getAllFriends(Integer person) 必须归还 getAllFriends(Integer person2) 也为了那个人的直接朋友。

因此,代码可能看起来像这样:

public class Test  {
        public static void main(String[] args) throws Exception {
            String input = "1<->6\n" +
            "2<->7\n" +
            "3<->8\n" +
            "4<->9\n" +
            "2<->6\n" +
            "3<->5";

            HashMap<Integer, ArrayList<Integer>> friends = processInput(input);  //getting data from the input string and storing it in a structured way
            System.out.println(getAllFriends(1, friends, new ArrayList<Integer>(){{add(1);}}));  //output: [1, 6, 2, 7]. Double brackets create an anonymous inner class, you add to the result the id of a person whose friends you're collecting
            }

        public static HashMap<Integer, ArrayList<Integer>> processInput(String input) throws Exception  {
            HashMap<Integer, ArrayList<Integer>> result = new HashMap<>();

            BufferedReader bufReader = new BufferedReader(new StringReader(input));
            String line=null;
            while( (line=bufReader.readLine()) != null )
            {
                Integer personLeft =  Integer.valueOf(line.substring(0, line.indexOf("<")));
                Integer personRight =Integer.valueOf(line.substring(line.indexOf(">")+1, line.length()));

                System.out.println(personLeft + ": " + personRight);

                if (!result.containsKey(personLeft))  {
                    result.put(personLeft, new ArrayList<Integer>());
                }

                result.get(personLeft).add(personRight);

                if (!result.containsKey(personRight))  {
                    result.put(personRight, new ArrayList<Integer>());
                }

                result.get(personRight).add(personLeft);
            }


            return result;

        }

        public static ArrayList<Integer>  getAllFriends(Integer person, HashMap<Integer, ArrayList<Integer>> friends, ArrayList<Integer> result)  {
            for (Integer personFriend: friends.get(person))  {
                    if (!result.contains(personFriend))  {
                        result.add(personFriend);  //add a person, if it wasn't added before
                        getAllFriends(personFriend, friends, result);  //check out that person's friends
                    }
            }

            return result;
        }
}