두 배열이 같은지 확인하십시오.

Question

두 배열이 동일한 지 알아 내기 위해 두 개의 배열이 있습니까?

해결 방법 중 하나는 해시 테이블을 사용하는 것입니다. 해시 테이블을 사용하여이를 어떻게 수행 할 수 있습니까?

Answer 1

이 C++ 태그를 사용했기 때문에 std::array에 오버로드 된 operator ==을 직접 사용할 수 있습니다.

Answer 2

사용 std::array :

std::array<int, 3> var = {{ 1, 2, 3 }}, 
        bar = {{ 4, 5, 6 }}; 
        baz = {{ 1, 2, 3 }}; 

std::cout << std::boolalpha << (var == baz) // true 
          << (bar == baz); // false 

Answer 3

그냥 algorithmical, 당신은 다음 단계를 따르 해시 테이블 같은 것을 사용하려면 다음과 수와 같은 크기의 새 테이블을 만듭니다

1. 을 가능한 문자/숫자를 비교할 배열의 내부에 두십시오 (예 : 비교할 배열에 ASCII 문자가있는 경우 255 개의 탭을 만들어야 함).
2. 새 테이블을 0으로 채 웁니다 (0). (대 루프)가 첫 번째 테이블을 통하여

3. 이동 인덱스 테스트 문자와 동일하여 해시 테이블의 필드를 증가 :

4. 번째 테이블 통과 for (int i=0; i<tab1.size; i++) hashtab[tab1[i]]++; (대 루프) 및 필드를 감소하여 해시 테이블.이 인덱스는 테스트 된 char과 같습니다. for (int i=0; i<tab2.size; i++) hashtab[tab2[i]]--;

5. 마지막으로 해시 테이블을 살펴 봅니다. 임의의 필드가 0과 다른 경우 테이블에는 동일한 요소가 들어 있지 않습니다. 그렇지 않으면 표에 동일한 요소가 포함됩니다.

false를 반환하지 않고 표의 끝에 도달하면 모두 0입니다. 예를 들어, 두 단어가 같은 글자로되어 있는지 확인할 수 있습니다 (정확히 같은 글자, 각 글자의 숫자가 같은 경우).

Answer 4

O (n)과 같은 방식입니다.

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <iterator> 
#include <random> 
#include <unordered_map> 

using namespace std; 

bool equal(const vector<int> &v1, const vector<int> &v2) 
{ 
    if (v1.size() != v2.size()) 
     return false; 

    unordered_map <int,int> map1, map2; 

    for (auto it = v1.begin(); it != v1.end(); ++it) 
     map1[*it]++; 

    for (auto it = v2.begin(); it != v2.end(); ++it) 
     map2[*it]++; 

    if (map1 != map2) 
     return false; 

    return true; 
} 

int main() 
{ 
    // create first array 
    vector<int> v1(10); 
    generate_n(v1.begin(), v1.size(), rand); 

    // create second array 
    vector<int> v2 (v1); 
    std::random_shuffle(v2.begin(),v2.end()); 

    // print arrays 
    copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, "\t")); cout << endl; 
    copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, "\t")); cout << endl; 

    cout << (equal(v1,v2) ? "equal" : "not equal") << endl; 

    return 0; 
}