java - 如何使该程序在线性时间内运行？

因此，我已经研究了几天的分配问题，并且发现使该程序在线性时间内运行非常困难。我已经在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）的方法。

有没有人有建议或提示？我真的缺少一些简单的东西吗？

提前致谢！

最佳答案

正如我在评论中所建议的那样，此解决方案的概念是：一遍遍，对每个要阅读的位置和要写的位置使用索引。读取一次重复块仅写入一次。当读取元素用完时，只需用-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++;
    }
  }
}