0

Вопрос

Мне дали задачу, текст и мое решение приведен ниже, задачу желательно решить с минимально возможной сложностью алгоритма.

Требуется, чтобы асимптотическое время работы полученного решения было линейным, или близким к линейному.

Я же реализовал решение за время O(n^2), несмотря на это, мое решение приняли, но, как сделать проще, никак не могу додуматься. Интересуюсь для своего развития, может кто-то подсказать пожалуйста - можно ли ее вообще решить за линейное время и как это сделать?

Задача

Имеется 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-ами (такой же как на входе). В качестве имени объединенного пользователя можно брать любое из исходных имен. Список email-ов пользователя должен содержать только уникальные email-ы. Параметры n и m произвольные, длина конкретного списка email-ов никак не ограничена. Требуется, чтобы асимптотическое время работы полученного решения было линейным, или близким к линейному.

Возможный ответ на задачу в указанном примере:
user1 ->[email protected],[email protected],[email protected],[email protected],[email protected]
user3 ->[email protected],[email protected]

Мое решение

public class Mail {
public static Map<String, Set<String>> merge(Map<String, Set<String>> mails) {
    if (mails.size() < 2) {
        return mails;
    }
    Map<String, Set<String>> temp = new HashMap<>();
    for (String key : mails.keySet()) {
        int f = 0;
        if (temp.size() == 0) {
            temp.put(key, mails.get(key));
        } else {
            for (String tempKey : temp.keySet()) {
                if (containsAny(temp.get(tempKey), mails.get(key))) {
                    Set<String> tmp = new HashSet<>(temp.get(tempKey));
                    tmp.addAll(mails.get(key));
                    temp.put(tempKey, tmp);
                    f++;
                }
            }
        }
        if (f == 0) {
            temp.put(key, mails.get(key));
        }
    }
    return temp;
}

private static boolean containsAny(Set<String> arr1, Set<String> arr2) {
    for (String value : arr1) {
        for (String s : arr2) {
            if (value.equals(s)) {
                return true;
            }
        }
    }
    return false;
}
}

Тесты

public class MailTest {
@Test
public void whenMerge() {
    Map<String, Set<String>> input = new HashMap<>();
    Set<String> user1 = new HashSet<>();
    Set<String> user2 = new HashSet<>();
    Set<String> user3 = new HashSet<>();
    input.put("User1", user1);
    input.put("User2", user2);
    input.put("User3", user3);
    Map<String, Set<String>> expected = new HashMap<>();
    Set<String> user2Ex = new HashSet<>();
    Set<String> user3Ex = new HashSet<>();
    expected.put("User2", user2Ex);
    expected.put("User3", user3Ex);
    input = Mail.merge(input);
    assertThat(input.get("User2"), is(expected.get("User2")));
    assertThat(input.get("User3"), is(expected.get("User3")));
}

@Test
public void whenNotMerge() {
    Map<String, Set<String>> input = new HashMap<>();
    Set<String> user1 = new HashSet<>();
    Set<String> user2 = new HashSet<>();
    Set<String> user3 = new HashSet<>();
    input.put("User1", user1);
    input.put("User2", user2);
    input.put("User3", user3);
    Map<String, Set<String>> expected = new HashMap<>();
    Set<String> user1Ex = new HashSet<>();
    Set<String> user2Ex = new HashSet<>();
    Set<String> user3Ex = new HashSet<>();
    expected.put("User1", user1Ex);
    expected.put("User2", user2Ex);
    expected.put("User3", user3Ex);
    input = Mail.merge(input);
    assertThat(input.get("User1"), is(expected.get("User1")));
    assertThat(input.get("User2"), is(expected.get("User2")));
    assertThat(input.get("User3"), is(expected.get("User3")));
}

@Test
public void whenOnlyOneUser() {
    Map<String, Set<String>> input = new HashMap<>();
    Set<String> user1 = new HashSet<>();
    input.put("User1", user1);
    HashMap<String, Set<String>> expected = new HashMap<>();
    Set<String> user1Ex = new HashSet<>();
    expected.put("User1", user1Ex);
    input = Mail.merge(input);
    assertThat(input.get("User1"), is(expected.get("User1")));
}

@Test
public void whenOnlyZeroUsers() {
    Map<String, Set<String>> input = new HashMap<>();
    Map<String, Set<String>> expected = new HashMap<>();
    input = Mail.merge(input);
    assertThat(input, is(expected));
}
}
2
  • Это задача про (двудольный) граф в котором нужно выделить компоненты связности. Поиск в ширину за линейное время. 4 фев 2021 в 16:42
  • Хммм, с графами я пока плотно не работал, видимо настал момент разбираться. Спасибо, @StanislavVolodarskiy!
    – NpB
    4 фев 2021 в 17:54

1 ответ 1

4

Решение через граф: по связям пользователь-почтовый адрес строим неориентированный граф, в нём отыскиваем компоненты связности.

Класс Graph<Node> строит граф (метод addEdge) и разбивает его на компоненты связности (метод components). Узел графа - пара вида (USER, 'user1') или (EMAIL, '[email protected]'). Каждый узел графа хранит множество своих непосредственных соседей.

Обход графа сделан в глубину. Вид обхода (в глубину, в ширину) не важен в нашей задаче, в глубину делать проще. Компонента в итоге содержит все связанные имена пользователей и их почтовые адреса.

Работает за линейное время:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;

public class ConnectivityComponents {

    public static void main(String... args) {
        Graph<Key> graph = new Graph<Key>();

        addRelations(graph, "user1", "[email protected]", "[email protected]", "[email protected]");
        addRelations(graph, "user2", "[email protected]", "[email protected]");
        addRelations(graph, "user3", "[email protected]", "[email protected]");
        addRelations(graph, "user4", "[email protected]", "[email protected]");
        addRelations(graph, "user5", "[email protected]");

        for (List<Key> keys : graph.components()) {
            for (Key key : keys) {
                if (key.type == KeyType.USER) {
                    System.out.print(key.value);
                    break;
                }
            }
            String sep = ": ";
            for (Key key : keys) {
                if (key.type == KeyType.EMAIL) {
                    System.out.print(sep + key.value);
                    sep = ", ";
                }
            }
            System.out.println();
        }
    }

    private static enum KeyType {
        USER, EMAIL;
    }

    private static class Key {
        public final KeyType type;
        public final String value;
        public Key(KeyType type, String value) {
            this.type = type;
            this.value = value;
        }
        @Override
        public int hashCode() {
            return Objects.hash(type, value);
        }
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Key)) {
                return false;
            }
            Key other = (Key)obj;
            return type == other.type && Objects.equals(value, other.value);
        }
    }

    private static void addRelations(Graph<Key> graph, String user, String... emails) {
        Key userKey = new Key(KeyType.USER, user);
        for (String email : emails) {
            graph.addEdge(userKey, new Key(KeyType.EMAIL, email));
        }
    }
}

class Graph<Node> {
    private final Map<Node, Set<Node>> graph = new HashMap<Node, Set<Node>>();

    public void addEdge(Node node1, Node node2) {
        getEdges(node1).add(node2);
        getEdges(node2).add(node1);
    }

    public List<List<Node>> components() {
        Set<Node> visited = new HashSet<Node>();
        List<List<Node>> components = new ArrayList<List<Node>>();
        for (Node node : graph.keySet()) {
            if (!visited.contains(node)) {
                components.add(component(visited, node));
            }
        }
        return components;
    }

    private Set<Node> getEdges(Node node) {
        if (graph.containsKey(node)) {
            return graph.get(node);
        }
        Set<Node> edges = new HashSet<Node>();
        graph.put(node, edges);
        return edges;
    }

    private List<Node> component(Set<Node> visited, Node node) {
        List<Node> component = new ArrayList<Node>();
        Stack<Node> stack = new Stack<Node>();
        stack.push(node);
        while (!stack.empty()) {
            Node n = stack.pop();
            if (!visited.contains(n)) {
                visited.add(n);
                component.add(n);
                for (Node nn : graph.get(n)) {
                    stack.push(nn);
                }
            }
        }
        return component;
    }
}
$ javac ConnectivityComponents.java && java ConnectivityComponents 
user1: [email protected], [email protected], [email protected], [email protected], [email protected]
user3: [email protected], [email protected]

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.