主页 / 问题 / 869430
Accepted
elik
Asked:2020-08-16 18:35:30 +0000 UTC2020-08-16 18:35:30 +0000 UTC

如何解决这个问题呢？

  • 772

下午好，我决定学习算法并完成书中的任务，但是我被这个任务打破了条件

Имеется n пользователей, каждому из них соответствует список email-ов (всего у всех пользователей m email-ов).
Например:
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru
user2 -> foo@gmail.com, ups@pisem.net
user3 -> xyz@pisem.net, vasya@pupkin.com
user4 -> ups@pisem.net, aaa@bbb.ru
user5 -> xyz@pisem.net

Считается, что если у двух пользователей есть общий email, значит это один и тот же пользователь. Требуется построить
и реализовать алгоритм, выполняющий слияние пользователей. На выходе должен быть список пользователей с их email-ами (такой же как на входе).
Возможный ответ на задачу в указанном примере:
user1 -> xxx@ya.ru, foo@gmail.com, lol@mail.ru, ups@pisem.net, aaa@bbb.ru
user3 -> xyz@pisem.net, vasya@pupkin.com
условие требует решения за ,близкое к линейному время

看起来很简单，我写了这样的东西

public class User {
    private String mName;
    private List<String> mAdress;

    public User(String mName,List<String>mAdress) {
        this.mName=mName;
        this.mAdress = mAdress;
    }

    public List<String> getmAdress() {
        return mAdress;
    }

    public void setmAdress(List<String> mAdress) {
        this.mAdress = mAdress;
    }

    public String getmName() {
        return mName;
    }

    public void setmName(String mName) {
        this.mName = mName;
    }
}


public class Main {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add("asnjvkn@mail.ru");
        arrayList.add("sfaf@mail.ru");
        arrayList.add("asnjvkn@mail.ru");
        arrayList.add("asnjvkn@mail.ru");
        arrayList.add("cxv@mail.ru");
        arrayList.add("asnjvkn@mail.ru");
        arrayList.add("vxcv@mail.ru");
        User user  = new User("user1",arrayList);
        ArrayList arrayList2 = new ArrayList();
        arrayList2.add("cxz@mail.ru");
        arrayList2.add("sfaxzvzf@mail.ru");
        arrayList2.add("asnjvkn@mail.ru");
        arrayList2.add("xv@mail.ru");
        arrayList2.add("cxv@mail.ru");
        arrayList2.add("asnjvkn@mvxail.ru");
        arrayList2.add("vxzvcv@mail.ru");
        User user2  = new User("user2",arrayList2);
        ArrayList arrayList3 = new ArrayList();
        arrayList3.add("sd@mail.ru");
        arrayList3.add("sfsdvaxzvzf@mail.ru");
        arrayList3.add("vd@mail.ru");
        arrayList3.add("xv@mail.ru");
        arrayList3.add("dsdvvs@mail.ru");
        arrayList3.add("asnjvkn@mvxail.ru");
        arrayList3.add("vxzvcv@mail.ru");
       User user3  = new User("user3",arrayList3);
       List<User> userList = new ArrayList<>();
       userList.add(user);
       userList.add(user2);
       userList.add(user3);

       userIdentification(userList);

    }



    public static void  userIdentification(List<User> userList){
     List<User> identifiedUser = new ArrayList<>();
     for (User singleUser: userList){
         for (int i = 0; i<singleUser.getmAdress().size();i++){
             for(User idenUser: identifiedUser){
              if (idenUser.getmAdress().contains(singleUser.getmAdress().get(i))){
                  System.out.println("true");
              }else{
                  System.out.println("false");
              }
             }
         }

     }

    }



}

但是这种情况需要在接近线性的时间内解决我的脑袋，告诉我如何实现这个

java

2 个回答

  1. Best Answer

    哈利建议的正确答案

    我们本质上是一个二分图。任务是找到它的连接组件。该问题通过相同的深度优先搜索从顶点数和边数之和（几乎相同的线性）在线性时间内解决。

    原始答案

    要存储电子邮件，请使用集合，例如Set

    然后是这样的（伪代码）

    ArrayList<User> out = ArrayList();

for(i=0;i<users.size;i++){
    for(j=0;j<out.size;j++){
        if(!users[i].emails.disjoint(out[i]){
            out[i].emails.addAll(users[i].emails);
            continue 2;
        }
    }
    out.add(users[i]);
}

    Collection.disjoint

    用户的简单枚举是O(n)，可以认为是一个下界。然后，对于主循环的每次迭代，在最坏的情况下，迭代顺序增加的输出列表，即 {O(1), O(2), O(3)...,O(n)}。总的来说，这个算法的边界是 O(n*log(n))。我承认每个用户的处理可以减少到 O(1)，但我不知道如何实现这一点。我没有考虑比较两个集合的操作的复杂性，因为我不知道它的实现。

    • 3

  2. 只需要知道集合：

    public static Map<User, Set<String>> convert(List<User> input) {
    // первая тут будут уники мейлы и пользователь который последний добавил его
    Map<String, User> one = new HashMap<>();
    Map<User, Set<String>> two = new HashMap<>();

    // тут будут уники юзеры и мейлы из первой карты где он засветился с таким мейлом
    // выгружаем всех юзеров попорядку
    for (User user : input
    ) {
        User temp = user;
        // выгружаем каждого юзера почту по одной
        for (String email : user.getMails()
        ) {
            // если почты нет еще в
            if (!one.containsKey(email)) {
                // то добавляем почту и юзера
                one.put(email, temp);
            } else {
                // но если есть то всю почту этого юзера кидаем тому кто ее уже принеc
                one.get(email).getMails().addAll(temp.getMails());
                for (String mail2 : one.get(email).getMails()) {
                    one.putIfAbsent(mail2, one.get(email));
                }
                break;
            }
                two.put(one.get(email), one.get(email).getMails());
        }

    }
    return two;
}
    • 2

相关问题