algorithm - 連数の和の性質

Question

[6,5,4,7,3] のような数値のリストがあるとします。配列に連続した数字が含まれていることをどのように確認できますか? 1 つの方法はもちろん、それらを並べ替えることです。または、最小値と最大値を見つけることができます。しかし、要素の合計に基づいて判断できますか? たとえば、上の例では 25 です。だれか助けてもらえませんか?

Answer 1

要素の合計だけでは十分ではありません。

代わりに、次のことを確認できます。

• すべての要素がユニークです。

およびいずれか：

• 最小値と最大値の違いが正しい

また

• 正しいすべての要素の合計。

アプローチ1

リストを並べ替えて、最初の要素と最後の要素を確認します。

一般に、これはO（n log（n））ですが、データセットが限られている場合は、カウントソートまたは基数ソートを使用してO（n）時間でソートできます。

アプローチ2

データを渡して、最高要素と最低要素を取得します。

通過するときに、各要素をハッシュテーブルに追加し、その要素が2回追加されているかどうかを確認します。これは多かれ少なかれO（n）です。

アプローチ3

ストレージスペース（ハッシュテーブル）を節約するには、おおよそのアプローチを使用します。

データを渡して、最高要素と最低要素を取得します。

あなたがするように、高い（ユーザー定義の読み取り）確率で各要素が異なると判断するアルゴリズムを実装します。そのようなアルゴリズムは数多く存在し、データマイニングで使用されています。これは、さまざまなアプローチを説明する論文へのリンクです。

Answer 2

配列の最大数と最小数の差が n-1 に等しい場合、配列内の数値は連続しています (ここで、n は配列のサイズです)。もちろん、最小数と最大数は O(n) で計算できます。