Найдите необычные элементы с помощью хеширования

Question

Я думаю, что это довольно частый вопрос, но я не нашел на него ответа с помощью хеширования в C ++.

У меня есть два массива одинаковой длины, которые содержат некоторые элементы, например :

A={5,3,5,4,2}
B={3,4,1,2,1}

Вот необычные элементы: {5,5,1,1}

Я пробовал этот подход - повторяя некоторое время l oop на обоих массивах после сортировки :

while(i<n && j<n) {
    if(a[i]<b[j])
            uncommon[k++]=a[i++];
    else if (a[i] > b[j])
            uncommon[k++]=b[j++];
    else {    
            i++;
            j++;
    }
}
while(i<n && a[i]!=b[j-1])
    uncommon[k++]=a[i++];
while(j < n && b[j]!=a[i-1])
    uncommon[k++]=b[j++];

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

Я пытался выполнить хеширование, но не смог полностью разобраться. вставить элементы из arr1 []:

set<int> uncommon; 
    for (int i=0;i<n1;i++) 
        uncommon.insert(arr1[i]); 

Для сравнения элементов arr2 []:

    for (int i = 0; i < n2; i++) 
        if (uncommon.find(arr2[i]) != uncommon.end()) 

Теперь я не могу отправить только эти элементы в необычный массив [] что необычно для них обоих.

Спасибо!

Answer 1

Прежде всего, std :: set не имеет ничего общего с хешированием. Наборы и карты представляют собой упорядоченные контейнеры. Реализации могут отличаться, но, скорее всего, это двоичное дерево поиска. Что бы вы ни делали, вы не станете быстрее n logn с ними - такая же сложность, как и сортировка. Если вас устраивает n logn и сортировка, я настоятельно рекомендую просто использовать алгоритм set_symmetric_difference https://en.cppreference.com/w/cpp/algorithm/set_symmetric_difference, он требует двух отсортированных контейнеров.

Но если вы настаиваете на реализация, основанная на хешировании, вы должны использовать std :: unordered_set или std :: unordered_map. Таким образом, вы можете быть быстрее, чем n logn. Вы можете получить свой ответ за n m времени, где n = a.size () и m = b.size (). Вы должны создать два unordered_set: hashed_a, hashed_b и в двух циклах проверить, какие элементы из hashed_a не находятся в hashed_b, а какие элементы в hashed_b нет в hashed_a. Здесь псевдокод:

create hashed_a and hashed_b
create set_result // for the result
for (a_v : hashed_a) 
  if (a_v not in hashed_b)
    set_result.insert(a_v)
for (b_v : hashed_b) 
  if (b_v not in hashed_a)
    set_result.insert(b_v)
return set_result // it holds the symmetric diference, which you need

UPDATE: как указано в комментариях, мой ответ не учитывается для дубликатов. Самый простой способ изменить его для дублирования - использовать unordered_map с ключами для элементов в наборе и значениями для количества встреч.

Answer 2

Решение без сортировки (и без хеширования, но вы, кажется, больше заботитесь о сложности, чем о самом хешировании) состоит в том, чтобы заметить следующее: необычный элемент e - это элемент, который находится ровно в одном мультимножестве.

Это означает, что мультимножество всех необычных элементов является объединением двух мультимножеств:

1. S1 = элемент в A, которого нет в B
2. S2 = элемент в B, который не в A

Используя std :: set_difference, вы получите:

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
int main() {
    std::multiset<int> ms1{5,3,5,4,2};


    std::multiset<int> ms2{3,4,1,2,1};

    std::vector<int> v;
    std::set_difference( ms1.begin(), ms1.end(), ms2.begin(), ms2.end(), std::back_inserter(v));
    std::set_difference( ms2.begin(), ms2.end(), ms1.begin(), ms1.end(), std::back_inserter(v));

    for(int e : v)
        std::cout << e << ' ';
    
    return 0;
}

Вывод:

5 5 1 1 

Сложность этого кода равна 4. (N1 + N2 -1) где N1 и N2 - размер мультимножеств.

Ссылки:

set_difference: https://en.cppreference.com/w/cpp/algorithm/set_difference

компилятор исследователь: https://godbolt.org/z/o3KGbf

Answer 3

Во-первых, вам нужно найти способ различать guish одних и тех же значений, содержащихся в одном массиве (например, 5 и 5 в первом массиве и 1 и 1 во втором массиве). Это ключ к снижению общей сложности, иначе вы не сможете добиться большего, чем O(nlogn). Хороший возможный алгоритм для этой задачи - создать объект-оболочку для хранения ваших фактических значений и поместить в ваши массивы указатели на эти объекты-оболочки с фактическими данными, чтобы адреса ваших указателей служили уникальным идентификатором для объектов. Эта упаковка будет стоить вам всего O(n1+n2) операций, а также дополнительного O(n1+n2) места.

Теперь ваша проблема в том, что в обоих массивах есть только элементы, уникальные для каждого из этих массивов, и вы хотите найти необычные элементы. Это означает (Union of both array elements) - (Intersection of both array elements). Следовательно, все, что вам нужно сделать, это объединить sh все элементы первого массива в карту ha sh (сложность O(n1)), а затем начать помещать все элементы второго массива в ту же самую ha. sh -карта (сложность O(n2)), обнаруживая коллизии (равенство элемента из первого массива элементу из второго массива). Этот шаг сравнения потребует O(n2) сравнений в худшем случае. Таким образом, для максимальной оптимизации производительности вы могли бы проверить размер массивов перед тем, как начать вставлять элементы в карту ha sh, и поменять местами массивы, чтобы первый pu sh занял место с самым длинным массивом. Общая сложность вашего алгоритма будет составлять O(n1+n2) нажатий (хешей) и O(n2) сравнений.

Реализация - самый скучный материал, поэтому я позволю вам это сделать;)

Answer 4

Вопрос может быть решен в O(nlogn) временной сложности.

АЛГОРИТМ

• Sort both array with merge sort in O(nlogn) complexity. You can also use sort-function. For example sort(array1.begin(),array1.end()).

• Now use two pointer method to remove all common elements on both arrays.

• Программа вышеуказанного метода

    int i = 0, j = 0; 
    while (i < array1.size() && j < array2.size()) { 
  
        // If not common, print smaller 
        if (array1[i] < array2[j]) { 
            cout << array1[i] << " "; 
            i++; 
        } 
        else if (array2[j] < array1[i]) { 
            cout << array2[j] << " ";  
            j++; 
        } 

        // Skip common element 
        else { 
            i++; 
            j++; 
        } 
    }

• Сложность вышеуказанной программы O(array1.size() + array2.size()). В худшем случае скажем O(2n)

• Приведенная выше программа выдает необычные элементы в качестве вывода. Если вы хотите сохранить их, просто создайте вектор и превратите sh в вектор.

• Исходная проблема ССЫЛКА