このプログラムを線形時間で実行するにはどうすればよいですか？

Question

私は今数日間割り当て問題に取り組んできました。私は、このプログラムを線形時間で実行することは非常に難しいと感じています。私はそれをO（n^2）で動作させましたが、私は完璧な得点を得たいと思います。

質問： 特定の数字の複製をネガティブに変更し、すべての複製を配列の最後に送信するように求められます。

For example, if the input array is [ 4 , 1 , 1 , 3 , 3 , 3 , 1 , 1 ], it 
    reads [ 4 , 1 , 3 , 1 , -1 , -1 , -1 , -1 ] after squeeze() completes. 

そして、ここに私のプログラムは次のとおりです。

int base = ints[ints.length -1]; 
    int count = 0; 
    for (int i = ints.length - 1 ; i > 0 ; i--) 
    { 
     if (base == ints[i-1]) 
     { 
      ints[i] = N_ONE; 
      count++; 
     } else { 
      base = ints[i-1]; 
     } 
    } 
    int count2 = 0; 
    for (int j = 0; (count) != count2 ; j++) 
    { 
     if (ints[j] == -1 && ints[j+1] != -1) 
     { 
      ints[j] = ints[j+1]; 
      ints[j+1] = N_ONE; 
      count2 = 0; 
      j = 0; 
     } else if (ints[j] == -1 && ints[j+1] == -1){ 
      count2++; 
     } 
    } 
} 

私の最初のループが効率的に機能し、それはとして-1のすべての重複番号を設定し、しかしだけでなく、私の第二のループは、リニア・ランタイムではありませんが、私それがより簡単な方法でできるように感じる。私は手でプロセスを書くことを試みたが、私はまだO（n^2）のメソッドしか考え出されていないようだ。

提案やヒントがありますか？本当にシンプルなものがありますか？

ありがとうございます！

Answer 1

このソリューションの背後にあるコンセプトは、私がコメントで示唆したとおりです。あなたが読んでいるところと書いているところのそれぞれにインデックスを使用して、それを1回のパスで行います。重複のブロックを読み取るために一度だけ書き込みます。読み込み要素を使い果たしたときは、配列の残りの部分を-1で埋めてください。

ここはJavaの実装です。ご覧のとおり、私は多くのテストを行っていません。

import java.util.Arrays; 

public class Test { 
    public static void main(String[] args) { 
    testIt(new int[]{}); 
    testIt(new int[]{4, 1, 1, 3, 3, 3, 1, 1}); 
    testIt(new int[]{1}); 
    testIt(new int[]{1,1}); 
    testIt(new int[]{1,2}); 
    } 

    public static void testIt(int[] in) { 
    System.out.println(Arrays.toString(in)); 
    squeeze(in); 
    System.out.println(Arrays.toString(in)); 
    System.out.println(); 
    } 

    public static void squeeze(int[] data) { 
    int readIndex = 0; 
    int writeIndex = 0; 
    while(readIndex < data.length){ 
     if(readIndex == 0 || data[readIndex] != data[readIndex-1]){ 
     // Need to store this one 
     data[writeIndex] = data[readIndex]; 
     writeIndex++; 
     } 
     readIndex++; 
    } 
    while(writeIndex < data.length){ 
     data[writeIndex] = -1; 
     writeIndex++; 
    } 
    } 
}