如何让这个程序在线性时间运行？

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