Как решить эту задачу?

225

05 ноября 2018, 17:00

Добрый день решил изучить алгоритмы и делаю задачи из книги , но вот с этой задачей сломал голову Условия

Имеется 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");
              }
             }
         }
     }
    }

}

но условие требует решения за ,близкое к линейному время Голову сломал подскажите как такое реализовать

Answer 1

Правильный ответ, предложенный Harry

Имеем по сути двудольный граф. Задача - поиск его компонент связности. Задача решается за линейное время от суммы числа вершин и числа ребер (та самая почти линейность) тем же поиском в глубину.

Оригинальный ответ

Для хранения email-ов используйте коллекцию типа 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), но не вижу путей, как этого достичь. Сложность операции сравнения двух наборов Set не учитываю, так как не знаю ее реализации.