我怎样才能让这个程序在线性时间内达到 运行？

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 填充数组的其余部分。

这是 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++;
    }
  }
}