從在C/C++在O（n）的時間的陣列中刪除重複

Question

假設我有像

int array[] = {1,1,1,4,5,7,7,9,11}; 

陣列我應該能夠除去所有的重複，因此我的輸出應爲{1,4 ，5,7,9,11}。

約束：

• 我不能分開使用任何形式的額外內存從變量
• 我應該能夠調整陣列
• 我不允許使用容器，如的Hashset或設置等：
• 如果在O（n）的時間

Answer 1

如果數組進行排序，然後該邏輯可以被應用於進行。

1. 有兩個指向數組開頭的指針（P1，P2）。
2. 遞增指針P2。檢查P2和P1指向的值是否相等。
3. 如果是，則進一步增加並達到P1和P2指向值不相等的點。現在轉到步驟5.
4. 如果否，則將P1分配給P2並從步驟2重複。
5. 現在，刪除P1和P2之間的元素。將P2分配給P1。

重複此過程，直到達到數組的終點。

Answer 2

遍歷數組並將每個元素與前一個元素進行比較。如果它一樣，你知道它是重複的。 保留另一個指針，用於複製數組中的每個唯一元素。例如， 1,1,4,5,7,7,9,11

保持兩個指針i和在陣列的起始Ĵ即1.
使用i遍歷數組和j來跟蹤獨特元件的。 最初， 1是唯一的，因此將[i]複製到[j]並同時增加。
接下來的1是重複的，所以只能增加j。
當遇到4個唯一的，所以將a [i]複製到a [j]（j指向第二個，即副本1）並且同時增加。
這樣做直到我完全遍歷數組。
a [0 ... j]給出所有獨特的元素。

複雜度：O（N）

Answer 3

如果您知道整數的最大值（MAX_INT_VALUE），因此不擔心內存的限制，這是一個讓我通過面試有點創造性的解決方案：

public int* removeDuplicates(int* array, int arraySize) { 

    short indexMarkers [MAX_INT_VALUE]; 
    int i = 0; 
    for (i=0; i<arraySize;i++) { 
     indexMarkers[array[i]]++; 
    } 

    int cursor = 0; 
    for(i=0; i<MAX_INT_VALUE;i++) { 
     if (indexMarkers[i] > 0) { 
      array[cursor] = i; 
      cursor++; 
     } 
    } 

    //resize array to be sizeof(int)*cursor 

    return array; 
} 

這個想法是讓數組中的項的值是indexMarkers數組的索引。然後你只是檢查值是否存在，以輸出新的數組。儘管如此，至少O（2N）。