Effiziente Art zu bestimmen, ob ein Vektor eine Untermenge eines anderen ist oder nicht?

Question

Gegeben zwei sortierte Vektoren bestehend aus eindeutigen Werten zwischen 0 und einigen bekannten 'n'. Und die Größe eines Vektors (set1) wird immer größer sein als die des Kandidatenvektors set2.

Abfrage: Ist zu bestimmen, ob set2 eine Teilmenge von set1 ist oder nicht?

Ist ihre bessere und effizientere Art, dies abgesehen von der folgenden Implementierung in C++ 11 zu tun?

#include <iostream> 
#include <vector> 


bool subSetCheck(std::vector<int> set1, std::vector<int> set2) { 

    //Set1 & 2 are always sorted and contain only unique integers from 0 to some known 'n' 
    //Set1 is always larger than Set2 in size 

    std::vector<int>::iterator it1 = set1.begin(); 
    std::vector<int>::iterator it2 = set2.begin(); 
    bool subSet = true; 
    for (; (it1 != set1.end()) && (it2 !=set2.end()) ;) { 

     if (*it1 == *it2) {++it1; ++it2;} 
     else if(*it1 > *it2) ++it2; 
     else ++it1; 
    } 

    if (it1 ==set1.end()) subSet = false; 

    return subSet; 
} 

int main() { 

    std::vector<int> set1{0,1,2,3,4}; 
    std::vector<int> set2{0,1,5}; 

    if (subSetCheck(set1,set2)) std::cout << "Yes, set2 is subset of set1." << std::endl; 
    else std::cout << "No! set2 is not a subset of set1." << std::endl; 

    return 0; 
} 

Answer 1

können Sie std::includes verwenden:

std::vector<int> a{1,2,3,4,5}; 
std::vector<int> b{1,2,6}; 
std::cout << std::includes(a.begin(), a.end(), b.begin(), b.end()) << std::endl; 

Answer 2

Ja, es gibt effizientere Wege. Die Antwort auf Ihre Frage hängt davon ab, ob Sie davon ausgehen, dass der Vektor die meiste Zeit eine Untermenge ist oder nicht.

Dies ist alles unter der Annahme, dass es keine doppelten Elemente gibt.

Schauen wir uns das mal an. Wenn vec2 zufällig eine Teilmenge von vec1 ist, dann wird die Überprüfung von O (vec1.size()) erforderlich sein, da Sie jedes Element betrachten müssen.

In diesem Fall ist Ihre Implementierung bereits fast optimal. Sie können die Binärsuche verbessern, um das erste übereinstimmende Element in vec1 anstelle der linearen Suche zu finden, wie Sie es jetzt tun.

Sobald Sie das Element gefunden haben, gibt es wirklich nicht viel mehr, was Sie tun können, anstatt alle Elemente zu durchlaufen und zu vergleichen.

Wenn auf der anderen Seite, können Sie davon ausgehen, dass die meiste Zeit set2 ist nicht ein susbet von set1, sollten Sie einen anderen Ansatz verfolgen.

Der Anfang ist der gleiche: Verwenden Sie die binäre Suche, um das erste Element von set2 in set1 zu finden.

Verwenden Sie dann die binäre Suche, um das letzte Element von set2 in set1 zu finden.

Überprüfen Sie dann, ob die Größe der Spanne mit der Größe von set2 übereinstimmt. Wenn nicht, können Sie sofort aussteigen.

Schließlich, wenn die Größe übereinstimmt, führen Sie den Element-für-Element-Vergleich durch.

Dinge werden komplizierter, wenn Sie doppelte Elemente haben, und herauszufinden, wie genau das zu tun ist als Übung für den Leser.