0

この質問は、入力が文字配列であり、サイズ 256 のハッシュを取得できる文字列内の最初の繰り返されていない文字を検索することに関連しています。

しかし、もし、

  • 配列の要素は広範囲の整数であり、ハッシュは非常にコストがかかる可能性があります。

  • 配列に異種の要素、整数、または文字が含まれている場合、ハッシュはこれにどのように対処できますか。

各要素に対して配列全体をスキャンする力ずくの方法を使用できますが、最悪の場合、O(n²) かかります。

他のアイデアはありますか？

4

2 に答える 2

1

まず、配列を昇順または降順で並べ替えます。次に、2 番目の要素から始まる並べ替えられた配列をループし、すべての要素を前の要素と比較して、それらが一致しているかどうかを確認します。

int[] numbers = {1, 5, 23, 2, 1, 6, 3, 1, 8, 12, 3};
Arrays.sort(numbers);

for (int i = 1; i < numbers.length; i++) {
    if (numbers[i - 1] == numbers[i]) {
        System.out.println("Repeated numbers are : " + numbers[i]);
    }
}
于 2015-11-08T10:21:21.763 に答える
1

オフライン バージョン: ベクトルを次のように並べ替えます。

vector<std::pair<int,int> > data;
for (int i=0;i<orignalVec.size();++i)
    data.push_back( make_pair(originalVec[i] , i ) );

次に、ベクトルをスキャンし、最初の値が同じで位置の値が最小のペアを探します。これにより、O(NlogN)

オンライン版です。std::map( O(NlogN)) std::unordered_map( )を使用しO(N)ます。

配列内の要素が広範囲の整数である場合、ハッシュは非常にコストがかかる可能性があります。

なんで？ハッシュはこの問題を回避するように設計されていますね。

配列に異種の要素、整数、または文字が含まれている場合、ハッシュはこれにどのように対処できますか。

これらのそれぞれに対して異なるハッシュ関数を記述します。、のような型の場合int、STL にはハッシュが組み込まれていると思います。floatstd::string

要素が比較操作をサポートしていない異種コンテナーの場合、私が思いつくことができるのはハッシュだけです。

于 2013-02-20T05:52:39.517 に答える