c++ - 判断两个数组是否相等

Question

给你两个数组来判断它们是否相等？

解决它的一种方法是使用哈希表。如何使用哈希表完成此操作？

Answer 1

使用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 2

像这样的事情会在 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;
}

Answer 3

由于您标记了此 C++，因此您可以直接使用重载operator ==的std::array.

Answer 4

如果它只是算法，并且您想使用哈希表之类的东西，请按照以下步骤操作：

1. 创建一个新表，其大小等于您比较的数组中可能包含的字符/数字的数量（例如，如果要比较的数组具有 ASCII 字符，则需要创建一个大小为 255 的制表符）。
2. 用零 (0) 填充新表。

3. 遍历第一个表（循环）并增加哈希表中索引等于测试字符的字段：for (int i=0; i<tab1.size; i++) hashtab[tab1[i]]++;

4. 遍历第二个表（循环）并减少哈希表的一个字段，该字段的索引等于测试字符。for (int i=0; i<tab2.size; i++) hashtab[tab2[i]]--;

5. 最后通过你的哈希表（循环）。如果其任何字段不为 0，则表不包含相同的元素。否则，表格确实包含相同的元素。

如果您到达表的末尾而没有返回 false，那么它全为零。例如，这可以用来查看两个单词是否由相同的字母组成（完全相同的字母，每个字母的数量相同）。