4

私は次の問題に取り組んでいます：

最小数の要素を削除して、指定された整数の配列をソート済みの配列に変換する必要があります。

例: [3,5,2,10,11] は、[3,5,10,11] の '2' を削除してソートされます。または [3,6,2,4,5,7,7] は '3','6' を削除してソートされます: [2,4,5,7,7] または '6','2' を削除してソートされます：[3,4,5,7,7]（どちらの方法でも2つの要素を削除するため、両方とも正しいです）。

私が考えたのは、各要素のカウンターを保持して、他の要素との競合の数を確認することでした。競合の意味: 最初の例では、数字 '3' と '5' にはそれぞれ 1 つの競合 (数字 '2' と) があり、数字 '2' には 2 つの競合 (数字 '3' と '5' と) があります。 . したがって、競合の配列を計算した後、競合の最大数を持つ要素を元の配列から削除し、すべての要素の競合が 0 になるまで残りの配列に対して繰り返します。

ただし、これは効率的な方法ではありません (場合によっては、間違った結果が生じる可能性があるとは思わない場合もあります)。

4

4 に答える 4

7

これは、最長増加サブシーケンス問題を巧妙に偽装したバージョンに過ぎないと思います。並べ替えられたシーケンスを持つ最小数の要素を削除すると、元の配列の最も長く増加するサブシーケンスが残ります。したがって、次のことができます。

  1. 最長増加サブシーケンスを見つけます (これには O(n log n) アルゴリズムが存在します)。
  2. そのサブシーケンスにないものをすべて削除します。

お役に立てれば！

于 2012-12-13T17:14:45.123 に答える
2

配列内の要素に基づいて DAG を構築できます。

  • 各要素 a[n] は頂点です。

  • (m < n) および (a[m] <= a[n]) である要素 (m,n) の任意のペアに対して、有向辺を追加します。

    最適化: ソートされた部分配列の単純なチェーンを構築できます。たとえば、a[m]<=a[m+1)<=a[m+2]<=a[m+3]>a[m+4] の場合、エッジ (m,m +2) および (m,m+3) は頂点 m の場合です。

ここでの目標は、有向非巡回グラフの線形時間解を持つ、グラフ内の最長パスを見つけることです。

アルゴリズムは、前述のウィキペディアのページとここでも説明されています。

于 2012-12-13T16:44:38.390 に答える
0

私は再帰的プログラミングでそれを行います。ここに私の疑似コードがあります:

/**
 *  sortedArray : an array already sorted.
 *  leftToSort : an unsorted array that need to be sorted/merged with sortedArray.
 *  first call to this function must be sortArrayByRemoval([], arrayToSort);
**/
public Integer[] sortArrayByRemoval(Integer[] sortedArray, Integer[] leftToSort){
    if(leftToSort.size==0){ 
        return sortedArray; //end of recursion
    }
    Integer candidate = leftToSort[0]; 
    if(candidate>=sortedArray[last]){ //append candidate to the sorted array
        return sortArrayByRemoval(sortedArray.append(candidate) , leftToSort.removeFirst());
    }else{
        //either we skip it
        Integer[] result1 = sortArrayByRemoval(sortedArray,leftToSort.removeFirst());
        //either we do back tracking
        Integer[] result2 = sortArrayByRemoval(sortedArray.removeLast(),leftToSort);
        //and finally we return the best choice (i.e. the longest array)
        return biggestArray(result1, result2);
    }
}

最も効率的ではないかもしれませんが、正しい答えが得られると思います。

于 2012-12-13T17:09:54.223 に答える
0

元の配列から文字通り何かを削除するという考えにとらわれていない場合は、元の数列の最も長く増加する部分列が必要です。これはよく知られた古典的な問題であり、文献や教科書で多くの例を見つけることができます。

(削除に行き詰まっている場合は、まあ... LCS を見つけて、LCS にないものをすべて削除してください。)

于 2012-12-13T17:17:47.060 に答える