Обновить
Комментарии 13
Интересно… И, хотя я ни разу в жизни не был на собеседовании, однажды пришлось решать нечто похожее — есть несколько файлов со строками (ну то есть множеств), надо найти уникальные строки, которые есть только в одном из файлой. Правда, я нисколько не думал — все очевидно:
cat * | uniq -u

Хороший вариант. Правда, мне он не подойдёт. Я копаю полубота для игры в судоку

Добрый день! Не до конца понятны условия задачи. Все найденные числа должны быть в одних и тех же множествах? Что если множество такое:


{{1, 2}, {2, 3}, {3, 4}}


Здесь выходит, что 2 есть в первом и втором векторе, а 3 во втором и третьем. Ну и мое решение на Wolfram


image

Конечно, нет. Они в разных
Увы, я не знаток Wolfram, хотя знание того, что не знаю я, всегда вызывает уважение. Примите решпект!

Как же неоптимально и сложно. Еще и куча ошибок. Все что надо — это для каждого числа подсчитать, в скольки множествах оно встречается и вывести те, где ответ n-1.


Я правда не понял, что у вас за "дупликаты" там. Если у вас есть "множество" {3, 0, 1, 2} (элемент 3 во множествах 0 и 1 но не 2), то не может быть "множества" {3, 1, 2, 0}, ведь 3 уже есть в 0-ом множестве!


Ваша же проверка на "дупликаты" в коде не работает никогда. Во-первых, там опечатка и вы меняете местами элементы в cur, хотя похоже подразумевалось cres. Во-вторых, первым элементом cres всегда будет число cur, которое уникально всегда, ведь это же элемент set! Поэтому проверки в result.find() у вас всегда вернут false. Еще у вас код result никогда не заполняет.


Для коррекнтного решения нужен один unorderd_map. Пройдитесь по всем вашим множествам и прибавьте 1 по ключу текущего числа. Если возможны повторения внутри одного множества, то надо их отсеять с еще одним unordered_set.


В итоге решение в k раз быстрее (если у вас k множеств и короче), да еще и работает:


vector<vector<int>> sets; // входные данные
unorderd_map<int, int> counts; // счетчики
unorderd_set<int> seen_numbers; // для дупликатов
vector<int> result; // ответ

for (size_t i = 0; i < sets.size(); ++i) {
  for (auto num : sets[i]) {
     // убрать, если дубликатов нет
     if (seen_numbers.find(num) != seen_numbers.end()) continue;
     seen_numbers.insert(num);

     counts[num]++;
  }
  seen_numbers.clear();
}
for (auto it : counts) {
  if (it.second + 1 == sets.size()) {
    result.push_back(it.first);
  }
}
За замечания спасибо. Я не ставил целью предоставить рабочий код. Цель была озвучить идею. В pet проекте воплощение этой идеи прекрасно работает. В оригинале там работа идет не с индексами, а с массивом булевских переменных. А уже на его основе заполняется cres. И в нём меняются местами элементы первый со вторым. С Вашим решением разберусь на свежую голову и отпишусь, хорошо?

Советую убрать статью в черновики, допилить и потом выложить.


Вам уже 2 человека написали, что идея у вас не оптимальная. Статья, состоящая только из идеи с обрезанным неоптимальным кодом с ошибками не очень хорошо смотрится.

Что-то сложно. Если уже используется N дополнительной памяти (all), то почему бы там не хранить просто счетчик числа вхождений. И за один проход — посчитали, за второй — выбрали. Один проход все равно делается, чтобы слить в all все сеты.

На питоне как-то так:
def calc(sets):
    cnt = {}
    for s in sets:
        for el in s:
            cnt[el] = cnt.get(el, 0) + 1

    return list([el for el,c in cnt.items() if c == len(sets)-1])


аналог питоновского dict — hashmap
Там так и сделано. Код не претендует на красоту и завершённость. Кстати, hashmap есть и в java

Ничего подобного. Вместо того, чтобы один раз пройтись по всем числам в каждом множестве и инкрементировать счетчики, вы проходитесь по всем возможным числам, а потом ищете, в каких множествах они есть. Ровно в 3 раза больше запросов к hash-set'ам.


А еще нормальное решение (посмотрите мой комментарий чуть выше) в 3 раза короче вашего некомпилируемого кода с ошибками, да еще и не полного (остатки которого вы предлагаете выпрашивать у вас в личке — это вообще позор).


Edit:
В дополнение: вся ваша статья — описание решения некоторой задачи и вы при этом вываливаете код, который "не претендует на красоту и завершённость". Какой вообще тогда смысл в статье?

Все еще осталась проблема с "дубликатами по положению". Такое ощущение, что этот cres у вас идет из какого-то древнего совсем странного решения, где вы перебирали множества в разных порядках.


Я вот про эту часть:


Последнюю фразу поясню. Предположим, имеется множества {1, 2, 3}, {3, 0, 4}, {5}. В данном искусственном примере на роль находки претендует элемент {3}, имеющийся в нулевом и первом множествах и отсутствующий во втором. Записать это можно также в виде множества {3, 0, 1, 2}. Буквально эта запись расшифровывается так: значение 3 имеется во множествах с индексами 0, 1, и отсутствует во множестве 2. Множество {3, 1, 2, 0} считается эквивалентным вышеприведённому и игнорируется.

В текущем решении вы перебираете все различные числа (до 64). Числа различные — первые элементы cres будут уникальными. cres вообще не нужен. Просто, если у вас cnt стал n-1 — то все, текущее число в ответ. Никаких повторений никак не может быть.


Во вторых, ваше решение до сих пор такое же неоптимальное, как в начале.
Вот вам аналогия: Задача подсчитать для каждого числа в массиве, сколько раз оно встречается в массиве. Правильное решение — пройтись по массиву и для каждого числа увеличить счетчик в массиве из 64 элементов. Ваше решение — пройтись по массиву и для каждого числа опять пройтись по массиву, и если числа совпали увеличить счетчик. Это аналогия. В вашей задаче не массив чисел, а массив множеств, но суть со вторым лишним вложенным проходом осталась.


Правильное решение тут завести один массив счетчиков на 64 элемента. Вместо построения битмапов — вам нужен один массив флагов на 64 элемента, который будет говорить, обработали ли вы число с таким значением в текущем множестве или нет. Если не обработали, делайте пометку в массиве флагов и увеличивайте счетчик.


Вот все решение (опять же, в 2 раза короче вашего и в 3 раза быстрее):


void PrepareData(const vector<vector<int> >& src, vector<int>& res)
{
  vector<int> cnt(MAX,0);
  for (const auto& cur_set : src) {
    int64_t was = 0;  // битмап для текущего множества.
    for (const auto& v : cur_set) {
      if ((was & (1 << v)) == 0) {
        was |= 1 << v;
        ++cnt[v];
      }
    }
    for (int i = 0; i < MAX; ++i) {
      if(cnt[i]+1 == src.size()) res.push_back(i);
    }
  }
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.