Функция, которая проверяет, если два массива идентичны

Question

Привет парней и девушка,

Я сделал функцию, что двойные проверки, если один и то же число в двух разных массивах присутствует, если происходят повторное число в массиве, не имеет значения.

Вот моя функция:

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; 
    } 
} 

В моей магистральный я в настоящее время только потому, что все жестко прописывать мне нужно работать в настоящее время является функцией. Так что в основном она выглядит следующим образом:

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."; 

Однако вы бы предположить, потому что число 4 в массиве б не присутствует в массиве а что было бы вернуть «do not for the same set», однако довольно удручающе это не делает. Я получаю "does form the same set". Я считаю, что это связано с моими операциями if в функции, но я не совсем уверен, как это сделать.

Thanks

Answer 1

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

Предположим, что sizeA составляет менее sizeB. Код, который у вас есть, проверяет, находится ли каждый элемент в a в b. Он не проверяет, находится ли каждый элемент в b в a. В сущности, вы проверяете, является ли a подмножеством b, а не a и b равными наборами.

Что вам нужно:

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; 
} 

Вы можете реорганизовать функция немного, чтобы избежать дублирования логики.

// 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

Если вы изменяете из фиксированного массива в контейнер, то вы можете воспользоваться стандартной библиотекой алгоритма процедур, а именно набором функций include или 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

С станд, вы можете просто написать его:

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

Все решения до сих пор, кажется, есть O (N^2) временная сложность; Вы можете сделать это в O (N * LogN) время с помощью карты:

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; 
} 

Вы даже можете сделать это в O (N) сложность время, если вы используете unordered_map (остальная часть логика).