Funktion, die prüft, ob zwei Arrays sind identisch

Question

Hallo zusammen Jungs und Mädchen,

Ich habe eine Funktion gemacht, dass eine doppelte überprüft, ob die gleichen Zahlen in zwei verschiedenen Arrays vorhanden sind, wenn es eine wiederholte Zahl in der Reihe ist, dass ist egal.

Hier ist meine Funktion:

bool sameSet(int arrA[], int arrB[], int sizeA, int sizeB) { 
    int temp; 
    if (sizeA < sizeB) { 
    for (int i = 0; i < sizeA; i++) { 
     bool exist = false; 

     for (int j = 0; j < sizeB; j++) { 
     if (arrA[i] == arrB[j]) { 
      exist = true; 
      break; 
     } // end of if 
     } // end of second for loop 

     if (!exist) return false; 

    } // end of first loop 

    return true; 
    } 

    else { 
    temp = sizeA; 
    sizeA = sizeB; 
    sizeB = temp; 

    // cout << "\nSize A is " << sizeA << " Size B is " << sizeB; 

    for (int i = 0; i < sizeA; i++) { 
     bool exist = false; 

     for (int j = 0; j < sizeB; j++) { 
     if (arrA[i] == arrB[j]) { 
      exist = true; 
      break; 
     } // end of if 

     } // end of second for loop 

     if (!exist) return false; 

    } // end of first loop 

    return true; 
    } 
} 

In meinem Haupt bin ich zur Zeit nur zu, weil alles, was ich zur Zeit arbeiten muß die Funktion ist. So in der Haupt sieht es so aus:

int sizea = 10, sizeb = 15; 
int a[] = {1, 3, 9, 16, 2, 5, 5, 5, 1, 16}; 
int b[] = {3, 9, 16, 9, 16, 16, 1, 1, 3, 2, 2, 5, 4, 16, 3}; 
cout << "The elements of the arrays a and b "; 
if (!sameSet(a, b, sizea, sizeb)) { 
    cout << "do not "; 
} 
cout << "form the same set."; 

aber Sie davon ausgehen würden, weil die Nummer 4 in Array b nicht in Array a ist, dass es die „do not for the same set“ zurückkehren würde, aber eher frustrierend ist es nicht. Ich bekomme "does form the same set". Ich glaube, es geht um meine if-Anweisungen in der Funktion, aber ich bin mir nicht sicher, wie ich das anstellen soll.

Dank

Answer 1

Die Logik, die Sie verwenden, ist fehlerhaft.

Nehmen wir an, sizeA ist weniger als . Der Code, den Sie überprüfen, ob jedes Element in a in b ist. Es wird nicht überprüft, ob jedes Element in b in a ist. Sie überprüfen im Wesentlichen, ob a eine Teilmenge von b ist, nicht ob a und b gleich sind wie Sätze.

Was Sie brauchen, ist:

bool sameSet(int arrA[], int arrB[], int sizeA, int sizeB) 
{ 
    // Check whether every element of A is in B 
    for(int i=0; i<sizeA; i++){ 
     bool exist = false; 

     for(int j=0; j<sizeB; j++){ 
     if(arrA[i] == arrB[j]) { 
      exist = true; 
      break; 
     } 
     } 

     if (!exist) return false; 
    } 

    // Check whether every element of B is in A 
    for(int i=0; i<sizeB; i++){ 
     bool exist = false; 

     for(int j=0; j<sizeA; j++){ 
     if(arrB[i] == arrA[j]) { 
      exist = true; 
      break; 
     } 
     } 

     if (!exist) return false; 
    } 

    return true; 
} 

Sie können die Funktion ein wenig Refactoring zu vermeiden, dass die Logik duplizieren.

// Function to check whether A is a subset of B 
bool isSubSet(int arrA[], int arrB[], int sizeA, int sizeB) 
{ 
    // Check whether every element of A is in B 
    for(int i=0; i<sizeA; i++){ 
     bool exist = false; 

     for(int j=0; j<sizeB; j++){ 
     if(arrA[i] == arrB[j]) { 
      exist = true; 
      break; 
     } 
     } 

     if (!exist) return false; 
    } 

    return true; 
} 

// Function to check whether A and B are same sets 
bool sameSet(int arrA[], int arrB[], int sizeA, int sizeB) 
{ 
    return (isSubSet(arrA, arrB, sizeA, sizeB) && 
      isSubSet(arrB, arrA, sizeB, sizeA)); 
} 

Answer 2

Wenn Sie von einer festen Anordnung an einem Behälter ändern, dann können Sie die Vorteile der Standard-Algorithmus Bibliotheksroutinen nehmen, nämlich den Satz Funktionen von include oder set_intersection.

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 
int main() 
{ 
    std::vector<int> v1{1,2,3,4,5,6,7,8}; 
    std::vector<int> v2{  5, 7, 9,10}; 
    std::vector<int> v3{ 2, 5, 7}; 
    std::sort(v1.begin(), v1.end()); 
    std::sort(v2.begin(), v2.end()); 
    std::sort(v3.begin(), v3.end()); 

    std::vector<int> v_intersection; 
    std::vector<int> v_includes; 

    std::set_intersection(v1.begin(), v1.end(), 
          v2.begin(), v2.end(), 
          std::back_inserter(v_intersection)); 

    for(int n : v_intersection) 
     std::cout << n << ' '; 
    std::cout << "\n";  
    std::cout << std::boolalpha << std::includes(v1.begin(), v1.end(), 
          v3.begin(), v3.end()); 
} 

Answer 3

Mit std, können Sie einfach schreiben:

bool isSameSet(const int arrA[], const int arrB[], int sizeA, int sizeB) 
{ 
    const std::set<int> setA{arrA, arrA + sizeA}; 
    const std::set<int> setB{arrB, arrB + sizeB}; 

    return setA == setB; 
} 

Answer 4

der Lösung Alle bisher scheinen O (N^2) Zeitkomplexität zu haben; Sie können durch die Verwendung einer Karte, um diese in O (N * log N) Zeit tun:

bool sameSet(int arrA[], int arrB[], int sizeA, int sizeB) 
{ 
    std::map<int,bool> mapA; 
    std::map<int,bool> mapB; 

    for (int i=0; i<sizeA; i++) 
    { 
     mapA[arrA[i]] = true; 
    } 

    for (int i=0; i<sizeB; i++) 
    { 
     mapB[arrB[i]] = true; 
    } 

    if (mapA.size() != mapB.size()) 
     return false; 

    std:map<int,bool>::const_iterator i, j; 
    for(i = mapA.begin(), j = mapB.begin(); i != mapA.end(); ++i, ++j) 
    { 
    if(*i != *j) 
     return false; 
    } 

    return true; 
} 

Sie selbst tun können, es in O (N) Zeitkomplexität, wenn Sie einen unordered_map verwenden (der Rest der Logik hält).