Алгоритм нахождения разности двух множеств A и B с размером n - PullRequest
Новая
       41

Алгоритм нахождения разности двух множеств A и B с размером n

0 голосов
/ 12 февраля 2019

Есть два набора A и B, и размер обоих наборов равен n.Как найти все элементы A, которых нет в B (AB), с O (n).Какую структуру данных я должен использовать (фильтр Блума?)

Ответы [ 2 ]

0 голосов
/ 12 февраля 2019

Вот один из способов вычисления разности множеств в сложности O (n) времени (и сложности пространства O (n)) без использования причудливой структуры данных, отличной от набора.Я предполагаю, что наборы A и B обладают способностью проверять членство за время O (1) (что типично для большинства реализаций HashSet).Этот алгоритм также не требует изменения наборов A и B.

Псевдокод алгоритма 

Goal: Calculate (A-B)
Input: Set A, Set B;
BEGIN:
    Create Empty Set C to contain (A-B).
    for each element a in Set A:
        if a does not exist in Set B:
            Add a to Set C;
    Return Set C;
END;

Сложность времени:

Это выполняется за O (n) сложности времени, потому чтовам нужно всего лишь перебрать все n элементов множества A.И для каждого из n элементов вы проверяете набор B на членство в O (1) раз.Это дает O (n) время выполнения для алгоритма.

Сложность пространства:

Сложность пространства равна O (n), поскольку используется новый набор C, который будет хранить до всех n элементов в решении.

Пример JavaРеализация 

import java.util.HashSet;

public class Tester {

    public static HashSet<String> setDifference(HashSet<String> A, HashSet<String> B) {
        HashSet<String> C = new HashSet<String>();
        for (String element : A) {
            if (!B.contains(element)) {
                C.add(element);
            }
        }
        return C;
    }

    public static void main (String[] args) {
        HashSet<String> A = new HashSet<String>();
        HashSet<String> B = new HashSet<String>();

        A.add("X");
        A.add("Y");
        A.add("Z");
        B.add("X");
        B.add("Y");

        HashSet<String> C = setDifference(A, B);
        // Set should only contain the element "Z"
        System.out.println(C);
    }

}
0 голосов
/ 12 февраля 2019

Учитывая, что оба являются наборами, вы должны использовать набор / hashset.Это позволит вам вычислить операцию в / в O(1).Фильтры Блума не подходят для такого рода проблем - они сообщают вам, если элемент определенно не входит в набор объектов, но все еще есть вероятность ложных срабатываний.Лучше использовать обычный хэш-набор, так как вам нужен точный ответ.

Для двух наборов вы можете вычислить разницу в наборе в O(min(|A|, |B|)).

Если A - это меньший набор, вы можетепройти по всем элементам в A и отбросить те, которые присутствуют в B.

Если B - меньшее множество, вы можете пройти по всем элементам в B и отбросить (из набора A) любой элемент, найденный в A.

...