使用O（nlogn）中的分隔和征服從陣列中刪除重複項

Question

您將獲得2010年奧林匹克票的n個請求的數組A.該陣列在請求時被排序，以便A（1）是第一個到達，A（2）是第二個到達等等。每個請求包含一個十位電話號碼。爲了公平起見，奧林匹克組織者制定了一條規定，每個電話號碼只能有一個請求。已經注意到數組A包含來自某些電話號碼的多個請求。寫一個O（nlogn）時間分割和征服算法，從A中刪除除了第一次接收到的來自同一個電話號碼的所有請求。最終輸出應該是數組A，其中包含來自唯一電話號碼的m個請求。 A中的請求也應該保持與刪除重複項之前的順序相同。

我得到如何做到這一點，如果數組按電話號碼排序，但我不明白如何以數據按請求時間排序時可能。

Answer 1

合併排序的一個簡單的修改將訣竅。合併排序是O（n log n）。它也是穩定的，這意味着具有相同鍵的項目將保持相同的相對順序。這裏唯一的區別是你想消除重複。對代碼的唯一更改是比較和複製項目。例如，一個標準的合併排序的內環看起來是這樣的：

while (leftIndex < leftMax && rightIndex < rightMax) 
{ 
    if (a[leftIndex] <= a[rightIndex]) 
    { 
     output[outputIndex] = a[leftIndex]; 
     ++leftIndex; 
    } 
    else 
    { 
     output[outputIndex] = a[rightIndex]; 
     ++rightIndex; 
    } 
} 

您會修改代碼，所以你不要複製等於項目：

while (leftIndex < leftMax && rightIndex < rightMax) 
{ 
    if (a[leftIndex] < a[rightIndex]) 
    { 
     output[outputIndex] = a[leftIndex]; 
     ++leftIndex; 
    } 
    else if (a[leftIndex] > a[rightIndex]) 
    { 
     output[outputIndex] = a[rightIndex]; 
     ++rightIndex; 
    } 
    else 
    { 
     // items are equal. 
     // increment the right, but don't copy anything 
     ++rightIndex; 
    } 
} 

你也可以做到這一點了標準合併排序，然後對排序後的數組執行最後一遍以移除重複項。

您可以使用Quicksort與自定義比較功能比較電話號碼和日期/時間。然後對已排序的數組執行最後一遍以刪除重複項。

Quicksort和Mergesort都被視爲分治算法。