合併排序刪除重複

我想通過合併排序排序數組，並排序時，刪除我認爲相等的元素。我遞歸調用合併排序然後合併。合併排序刪除重複

我得到這一點，發現a和c是重複。

a b | c d

我根據某些標準確定我想要哪一個，我選擇c。我增加右手計數器和左手計數器並比較b和d。說我選擇d，然後選擇b。我希望我的最終名單隻有具備的要素

c d b

然而，正在發生的事情是在接下來的遞歸調用，start和end是0和3等等d是在下次調用數組中列出兩次。與合併過程一起使用的數組是：

c d b d

這是代碼。提前致謝。

private static void merge(int[] data, int start, int mid, int end) 
{ 
    int firstCopied=0; 
    int secondCopied=0; 
    int index=0; 
    int length=end-start+1; 

    int[] temp = new int[end-start+1]; 
    int firstSize=mid-start+1; 
    int secondSize=end-mid; 

    while(firstCopied < firstSize && secondCopied < secondSize) 
    { 
     if(data[start+firstCopied] < data[mid+1+secondCopied]) 
     { 
      temp[index++] = data[start+firstCopied]; 
      firstCopied++; 
     } 

     else if(data[start+firstCopied] > data[mid+1+secondCopied]) 
     { 
      temp[index++] = data[mid+1+secondCopied]; 
      secondCopied++; 
     } 

     else if(data[start+firstCopied]==data[mid+1+secondCopied]) 
     { 
      boolean result = PickOne(); 

      if(result) 
      { 
       temp[index++] = data[start+firstCopied]; 
      } 
      else 
      { 
       temp[index++] = data[mid+1+secondCopied]; 
      } 

      firstCopied++; 
      secondCopied++; 
      length--; 
     } 
    } 
    while(firstCopied < firstSize) 
    { 
     temp[index++] = data[start+firstCopied]; 
     firstCopied++; 
    } 

    while(secondCopied < secondSize) 
    { 
     temp[index++] = data[mid+1+secondCopied]; 
     secondCopied++; 
    } 

    for(int i=0; i<length; i++) 
    { 
     data[start+i]=temp[i]; 
    } 

}

來源

2013-05-08 user1317750

'PickOne（）'做了什麼？ – 2013-05-08 07:00:21

在我看來，mergesort已經足夠複雜了，而沒有將專用代碼交織在一起刪除重複。我會建議兩個單獨的函數：首先合併數據，然後刪除重複項，這大概在排序數據中是連續的，因此很容易找到。 – Simon 2013-05-08 08:01:10

你已經標記了這個C和C++，但是'private static void ...'和'int [] temp = new int [end-start + 1];'表明這是另一種語言。你實際使用哪種語言？ – 2013-05-08 10:03:02

您的merge從概念上改變了數組的長度。但是沒有代碼實際截斷data。我建議你返回length（而不是void），並使用一些最終的後處理步驟將數據截斷爲最終長度，或者至少避免打印那些過去結束的元素。

來源

2013-05-08 08:57:23 MvG

C++標準庫的哲學是使用算法好一件事。最好遵循這種方法，因爲它會導致更多的可重用代碼。

E.g.這裏有一個合併的草圖，然後調用std::unique

template<typename BiDirIt> 
void merge_sort(BiDirIt first, BiDirIt last) 
{ 
    auto const N = std::distance(first, last); 
    if (N < 2) return; 

    // sort each part individually, then merge back in-place 
    auto middle = first + N/2; 
    merge_sort(first, middle); 
    merge_sort(middle, last); 
    std::inplace_merge(first, middle, last); 
}  

int data[] = { /* your data */ }; 
merge_sort(std::begin(data), std::end(data)); 

auto it = std::unique(std::begin(data), std::end(data)); 
for (auto ut = std::begin(data); ut != it; ++ut) { 
    // process unique data 
}

如果你的數據是在一個std::vector，而不是C-數組，你可以調用v.erase(v.begin(), it);實際刪除非唯一的數據也是如此。

來源

2013-05-08 09:08:19 TemplateRex

我很驚訝你使用自定義代碼進行排序，並依靠默認設置刪除獨特的元素。我寧願這樣做，因爲'std :: sort'或'std :: stable_sort'應該給出相同的結果，但是故意在兩個相等的元素之間進行選擇（比如'PickOne'大概是這樣）不是零件['std :: unique']的工作（http://en.cppreference.com/w/cpp/algorithm/unique）。 – MvG 2013-05-09 18:49:43

@MvG我寫了一個自定義的'merge_sort'來展示用遞歸+ std :: inplace_merge'編寫它是多麼容易，而不是替代'std :: stable_sort'。也許我掩飾了「PickOne」選擇標準，但我的答案的主要觀點是讓一個算法做一件事。 – TemplateRex 2013-05-09 20:14:29

確保[start，mid]和[mid + 1，end]中的元素先排序並唯一。否則，您的代碼運行後會出現重複項。

來源

2013-05-08 09:19:34

合併排序刪除重複

回答

相關問題