16
Авг
2018

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

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

Имеется n пользователей, каждому из них соответствует список email-ов (всего у всех пользователей m email-ов).
Например:
user1 -> [email protected], [email protected], [email protected]
user2 -> [email protected], [email protected]
user3 -> [email protected], [email protected]
user4 -> [email protected], [email protected]
user5 -> [email protected]

Считается, что если у двух пользователей есть общий email, значит это один и тот же пользователь. Требуется построить
и реализовать алгоритм, выполняющий слияние пользователей. На выходе должен быть список пользователей с их email-ами (такой же как на входе).
Возможный ответ на задачу в указанном примере:
user1 -> [email protected], [email protected], [email protected], [email protected], [email protected]
user3 -> [email protected], [email protected]
условие требует решения за ,близкое к линейному время

Вроде легко я написал нечто такое

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("[email protected]");
        arrayList.add("[email protected]");
        arrayList.add("[email protected]");
        arrayList.add("[email protected]");
        arrayList.add("[email protected]");
        arrayList.add("[email protected]");
        arrayList.add("[email protected]");
        User user  = new User("user1",arrayList);
        ArrayList arrayList2 = new ArrayList();
        arrayList2.add("[email protected]");
        arrayList2.add("[email protected]");
        arrayList2.add("[email protected]");
        arrayList2.add("[email protected]");
        arrayList2.add("[email protected]");
        arrayList2.add("[email protected]");
        arrayList2.add("[email protected]");
        User user2  = new User("user2",arrayList2);
        ArrayList arrayList3 = new ArrayList();
        arrayList3.add("[email protected]");
        arrayList3.add("[email protected]");
        arrayList3.add("[email protected]");
        arrayList3.add("[email protected]");
        arrayList3.add("[email protected]");
        arrayList3.add("[email protected]");
        arrayList3.add("[email protected]");
       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");
              }
             }
         }

     }

    }



}

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

Источник: https://ru.stackoverflow.com/questions/869430/%D0%9A%D0%B0%D0%BA-%D1%80%D0%B5%D1%88%D0%B8%D1%82%D1%8C-%D1%8D%D1%82%D1%83-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D1%83

Тебе может это понравится...

Добавить комментарий