ホームページ  >  記事  >  Java  >  Javaで配列内で繰り返される数値のクエリを実装する方法

Javaで配列内で繰り返される数値のクエリを実装する方法

不言
不言転載
2018-10-23 15:14:263606ブラウズ

この記事の内容は、Java で配列内の繰り返しの数値をクエリする方法に関するものです。必要な方は参考にしていただければ幸いです。

質問 1: 配列内で重複する数値を見つけます。

長さ N の配列内のすべての数値は 0-n-1 の範囲内にあります。配列内の一部の数値は繰り返されますが、いくつの数値が繰り返されるかはわかりません。数値が繰り返される回数 配列内で繰り返される数値を見つけてください。

解決策 1: この配列をソートする ソートされた配列から重複する数値を見つけるのは非常に簡単です。ソートされた配列を最初から最後までスキャンするだけで、長さ N の配列をソートするには O(nLogn) 時間がかかります。

解決策 2: ハッシュ テーブルを使用して問題を解決します。数値がスキャンされるたびに、その数値がハッシュ テーブルにあるかどうかを判断します。アルゴリズムは O(N) ですが、その時間効率はサイズ O(N) のハッシュ テーブルを犠牲にします。

解決策 3: 配列を並べ替えて、配列内の各数値を最初から最後までスキャンします。添字 i の数値がスキャンされたときに、この数値 (m) が i と等しいかどうかを比較します。等しい場合、m の値が i に支払われます。等しくない場合は、繰り返される値がすべて見つかるまで、m の添字に対応する値と比較します。

Javaで配列内で繰り返される数値のクエリを実装する方法

以上がJavaで配列内で繰り返される数値のクエリを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はsegmentfault.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。