Вопрос
Мне дали задачу, текст и мое решение приведен ниже, задачу желательно решить с минимально возможной сложностью алгоритма.
Требуется, чтобы асимптотическое время работы полученного решения было линейным, или близким к линейному.
Я же реализовал решение за время 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));
}
}