Оптимальный способ объединить два вектора в vc ++

Question

Я нахожу лучшую логику для объединения 2 векторов.

vector_A[id][mark1];
vector_B[id][mark2];

vector_A: id = [300 , 502, 401 , 900 , 800 ,700 , 250 , 001] 
          mark1 = [55 , 50 , 30 , 28 , 25 , 11 , 04 , 03]

vector_B: id = [800 , 005 , 502 , 925 ,025 ,300 , 52] 
          mark2 = [75, 60 , 50 ,35 , 30 , 25 , 04]

Правило комбинирования: Если одинаковый идентификатор находится в двух векторах, добавьте mark1 и mark2.Если не просто отобразить.

vector_combined: id = [800 , 300 , 502 , 005 , 925 , 401] 
                 mark_combine = [100, 80 , 100 , 60 , 35 ,30]

Пожалуйста, помогите мне с оптимальным решением.

Answer 1

Здесь, на SO, мы будем рады помочь людям с подсказками по домашним вопросам, при условии, что они заранее определили вопрос в качестве домашней работы - как и вы:)

Как сейчас, чтобы найти соответствие для конкретного элемента в vector_A, вам нужно отсканировать каждый элемент vector_B. Таким образом, если в vector_A есть m элементов, а в vector_B n элементов, то для поиска всех совпадений потребуется O (mn) времени - довольно медленно.

Предположим, мы сортируем эти два вектора и соответственно переупорядочиваем mark1 и mark2. Теперь вы заметили, что при поиске определенного элемента в vector_B вы можете остановиться, как только доберетесь до слишком большого элемента - поскольку вы знаете, что все последующие элементы должны быть еще больше. Это сэкономит время.

На самом деле вы можете пойти еще дальше и посмотреть только на 1-й элемент vector_A и vector_B. Давайте назовем их a и b соответственно. Теперь может произойти только один из 3 случаев:

1. a < b. В этом случае мы можем заключить, что a не может появиться в любом месте в vector_B, поскольку все более поздние элементы будут как минимум столь же большими, как b, что уже слишком велико.
2. a > b. Точно так же мы можем заключить, что b не может появиться в любом месте в vector_A, поскольку все последующие элементы будут по крайней мере столь же большими, как a, что уже слишком велико.
3. a = b. В этом случае ясно, что это число появляется в обоих векторах!

Учитывая, что сортировка занимает всего O (nlog n) времени, это должно дать вам подсказку для более быстрого алгоритма. Если вам нужна дополнительная помощь в понимании, оставьте комментарий.

Answer 2

Я не уверен, правильно ли я понимаю вашу проблему ... но вы случайно не ищете std :: set_intersection ?

Алгоритм требует, чтобы ваши диапазоны были отсортированы,Итак, сортируйте их и кормите их set_intersection