3

のような配列が与えられ[15, 14, 12, 3, 10, 4, 2, 1]ます。どの要素が順不同であるかを判断して削除するにはどうすればよいですか (この場合は 3 番です)。リストをソートしたくありませんが、外れ値を検出して削除します。

もう一つの例：

[13, 12, 4, 9, 8, 6, 7, 3, 2]

＃4と＃7を削除できるようにしたいので、最終的には次のようになります。

[13, 12, 9, 8, 6, 3, 2]

このシナリオがある場合に発生する問題もあります。

[15, 13, 12, 7, 10, 5, 4, 3]

7 または 10 を削除して、この配列をソートすることができます。

一般に、私が解決しようとしている問題は、数値の読み取り値のリストが与えられた場合です (一部はかなりずれている可能性があります)。配列には、一般的な傾向線に沿った値のみを含め、外れ値を削除したいと考えています。これを行う簡単な方法があるかどうか疑問に思っています。

4

2 に答える 2

3

higuaro によって記述された単純なアルゴリズムは、正しいシーケンスを生成するのに役立ちます。

index の各要素についてi、ifa[i] < a[i + 1]の場合、その要素を単純に削除できますa[i]。

for(int i = 0; i < size; i++)
    while(a[i] < a[i + 1]){
       remove a[i];
       i--;
    }

ただし、このアプローチでは、削除される要素の数が最小であることを保証できません。たとえば、このシーケンス [10, 9, 8, 100, 1, 0] の場合、8 を削除してから 9 を削除してから 10 を削除するのではなく、100 を削除するのが最適です。

削除する要素の最小数を見つけるには、最長減少サブ シーケンスを見つける必要があることに気付きます。これは、ソリューションがここで説明されている従来の最長増加サブ シーケンスに似ています。

于 2015-08-26T02:54:38.043 に答える