如何讓這個程序在線性時間運行？

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