2

intの配列を受け取るsmoosh（）メソッドを終了しようとしています。完了すると、配列には同じ番号が含まれているはずですが、配列に2つ以上の連続した重複番号がある場合は、それらは番号の1つのコピーに置き換えられます。したがって、smoosh（）が実行された後、配列内の2つの連続する数値が同じになることはありません。

配列の最後にある未使用の要素はすべて-1に設定されます。

たとえば、入力配列が

[ 1 1 0 0 4 4 5 0 0 0 7 ]

それは読む

[ 1 0 4 5 0 7 ]

smoosh（）が完了した後。

メソッドのシグネチャは次のとおりです。publicstaticvoidsmoosh（int [] ints）

私はこのようにそれを行うことができました：

for (int i=0; i<ints.length-1; i++) {
    if (ints[i+1]==ints[i])
        ints[i]=-1;
}
for (int i=0; i<ints.length-1; i++) {
    if (ints[i]==-1) {
        for (int j=i+1; j<ints.length; j++) {
            if (ints[j]!=-1) {
                //swap ints[j] and ints[i] and then break;
            }
        }
    }
}

ただし、これはO（n2）時間になります（ほぼ適切ですが）。

これを行うには、O（n）を配置する必要があるように感じますが、その方法がわかりません。誰かがO（n）インプレースアルゴリズムを思いつくことができますか？（明らかに、処理を支援するために同じサイズの別の配列を作成すると、O（n）を簡単に取得できますが、それが適切に行われていないため、私が探しているものではありません...）

ありがとう！

4

3 に答える 3

4

基本的には以下のとおりです。このO（n）時間、O（1）空間の「アルゴリズム」は、実際にはPythonコードです。これは、ラムダなどの複雑なものをすべて回避する限り、基本的なアルゴリズムを教えるのに非常に適した言語だからです。

私は実際にそれを使って8歳の息子に教えています。彼は私が一日中仕事でしていることに興味を示しているからです。

array = [1, 1, 0, 0, 4, 4, 5, 0, 0, 0, 7]

print array

count = len (array)
last = array[0] - 1
toidx = 0
for fromidx in range (0, count):
    if array[fromidx] != last:
        array[toidx] = array[fromidx]
        toidx = toidx + 1
        last = array[fromidx]
while toidx < count:
    array[toidx] = -1
    toidx = toidx + 1

print array

これの出力は次のとおりです。

[1, 1, 0, 0, 4, 4, 5, 0, 0, 0, 7]
[1, 0, 4, 5, 0, 7, -1, -1, -1, -1, -1]

あなたの仕様が求めるように。

基本的に、配列を介して2つのインデックスを実行し、fromixインデックスは何があっても1つ進みます。の値が最後に転送されtoidxた値と異なる場合にのみ、インデックスが進みます。fromidx最後に転送されたものの初期値は、最初の要素が確実に転送されるように、最初の要素とは異なる値に設定されます。

つまり、その条件が真である各反復で、インデックスの値がfromインデックスにコピーされ、toidxインデックスtoidxがインクリメントされ、last値が更新されます。の値fromidxが最後に転送された値と同じである場合、toidxインデックスは更新されません。

次に、最後に、残りのすべての値が-1に設定されます。

仕様では、配列の残りの部分に-1を入力する必要があるため、上記のコードでこれを実行しました。

ただし、サンプル結果には負の値が含まれていないため、配列を埋めるのではなく切り捨てる必要がある場合は-1、基本的にwhile最後のループを配列の切り捨てに置き換えて、サイズをに変更しますtoidx。

Pythonでは、次のような方法でそれを行うことができます。

array = array[0:toidx]
于 2012-10-01T03:54:10.230 に答える
3

内側のループは必要ありません。最後にアクセスした値を追跡し、「新しい」番号が見つかるまでスキップを開始する必要があります。例：擬似コード

previous = null;
newarray = array();
newpos = 0;
for (i = 0; i < oldarray.length; i++) {
   if (oldarray[i] == previous) {
      continue; // got a duplicate value, so skip it.
   } else {
      newarray[newpos++] = oldarray[i];
      previous = oldarray[i];
   }
}
for (i = newpos; i < oldarray.length; i++) {
   newarray[i] = -1; // fill in any empty slots
}

これで、O（n）になりました。

于 2012-10-01T03:54:48.277 に答える
1

LinkedList代わりにを使用する場合は、 ListIteratorforループを使用して、前の値の値をリストに格納し、ListIterator.removeそれが現在の値と等しいかどうかを呼び出すことができます。

于 2012-10-01T03:56:25.420 に答える