0

C++ で整数配列を特徴付けることは可能ですか? 特徴付けが完了すると、同じ要素セットを含む配列は同じ特性を持ちます。私はhashcodeの行について考えていました。各ハッシュコードは配列を一意に識別します!

たとえばary[]={4,5,3,2,4}、ary_two[]={4,4,2,3,5}両方とも同じ特性/ハッシュコードを持つ必要があります!

私はこの質問を解決しようとしています (インタビューで尋ねられました): 多数の可変サイズの配列が生成されています。各配列について、この配列と同じ要素を含む前に配列に遭遇したかどうかを判断してください!

4

2 に答える 2

2

std::hashを調査します。あなたはおそらくそれをオーバーロードして、やりたいことをすることができます。たとえば、値を持つ配列が必要で{4, 5, 3, 2, 4}、{4, 4, 2, 3, 5}同じ値にハッシュする場合は、次のように特殊化できます。

template<> struct hash<std::array<int, 5>>
{
    size_t operator()(const std::array<int, 5> &ary) const
    {
        return std::accumulate(std::begin(ary), std::end(ary), 0U) * 16777619;
    }
};
于 2012-11-05T00:24:38.483 に答える
2

考えられる解決策の 1 つは、要素のハッシュ自体を使用することです (配列の内容がハッシュ可能であると仮定します)。xor次に、それらを適切な関数 (たとえば anまたは better yet )と一緒に折りたたむだけ+です。折り畳み関数が可換かつ結合的であることを確認してください。そうしないと、配列の順序によって違いが生じます。

于 2012-11-05T00:18:53.550 に答える