如何使用合并排序删除重复项？

我使用递归合并排序来排序链接列表，但在合并排序期间我想删除重复项。 任何人都知道如何实现这一目标？

我正在使用C代码。

Answer 1

在合并排序中，您将两个（或更多）已排序的列表重复应用以下规则：

• 找到每个输入列表顶部的较小/最少的项目，如果有关系，则选择任何最低项目
• 从列表中删除该项目
• 将其添加到输出列表中

要删除重复项，您只需稍微修改规则：

• 找到每个输入列表顶部的较小/最少的项目，如果有关系，则选择任何最低项目
• 从列表中删除该项目
• 如果它与您添加到输出列表中的最后一项相同，则将其丢弃
• 否则，将其添加到您的输出列表

这将确保输出列表中没有两个连续项目相同，并且其中的项目按顺序排列，这就是您所追求的。

Answer 2

要使用合并排序来删除重复项，您将忽略在合并过程中重复的元素。

Answer 3

考虑mergesort中的合并function。

在合并过程中，您当然要将元素相互比较。

说服自己，如果你要合并2个排序列表A和B，并且如果两个列表包含相同的值x，那么将会发生两个相同的元素将相互比较。 如果你想要一个certificate，我的方法是表明，如果有一个案例没有比较两个相同的元素，那么其中一个或两个列表实际上是未排序的。 通过矛盾certificate，宝贝！

因此，您可以轻松检测到两个列表中有两个相同元素被合并的情况。

接下来，说服自己，如果刚刚合并的两个列表中有两个相同的元素，那么最终它们将被合并在一起，并且将检测到相同的元素。 这基本上是归纳的certificate—如果没有别的，显然最后的合并（将长度为n / 2和n / 2的排序列表合并到长度为n的最终列表中）将把这些元素组合在一起。

最后，如果你递归到n = 1或n = 0的情况，说服自己不能存在具有两个相同元素的单数列表。 这又是归纳法，因为任何较大的列表首先必须在第一个大段落中描述的“过滤”过程中存活下来。

如果您确信这三件事情，那么很明显Steven或Tim的解决方案非常适合。

Answer 4

使用C ++但你可以使用数组而不是C的向量

#include  #include  // merge 2 arrays using a temp array void merge (std::vector& v, std::vector& tmpArray, int left, int center, int right ) { int leftPos = left; int leftEnd = center; int tmpPos = leftPos; int rightEnd = right; int rightPos = center + 1; // finger matching algo left and right while ( leftPos <= leftEnd && rightPos <= rightEnd ) { // this first if block here for equals is what does your duplicate removal magic if ( v[leftPos] == v[rightPos] ) { tmpArray[tmpPos++] = std::move(v[leftPos++]); ++rightPos; } else if ( v[leftPos] < v[rightPos] ) tmpArray[tmpPos++] = std::move(v[leftPos++]); else tmpArray[tmpPos++] = std::move(v[rightPos++]); } // copy rest of left while ( leftPos <= leftEnd ) tmpArray[tmpPos++] = std::move(v[leftPos++]); // copy rest of right while ( rightPos <= rightEnd ) tmpArray[tmpPos++] = std::move(v[rightPos++]); // copy tmp array back to array int numElements = right - left + 1; for ( int i = 0; i < numElements; ++i, --rightEnd) v[rightEnd]=std::move(tmpArray[rightEnd]); } void mergeSort ( std::vector& v, std::vector& tmpArray, int left, int right ) { if ( left < right ) { auto center = left + (right - left)/2; mergeSort(v, tmpArray, left, center); mergeSort(v, tmpArray, center+1, right); merge ( v, tmpArray, left, center, right ); } } void mergeSort (std::vector& v) { int sz = v.size(); std::vector tmpArray ( sz, 0 ); mergeSort (v, tmpArray, 0, sz-1); } int main () { std::vector v { 7,8,6,5,4,3,9,12,14,17,21,1,-2,-3,-3,-3,-9,10,11 }; mergeSort ( v ); for ( auto&i : v) std::cout << i << " " ; std::cout << std::endl; } 

Answer 5

使用Collection Iterators而不仅仅是向量更新我的原始答案，使用一些更通用的代码。

 // merge a sort collection template void mergeCollection(CollectionT & collection, CollectionT & tmpCollection, typename CollectionT::iterator first, typename CollectionT::iterator mid, typename CollectionT::iterator last) { using IteratorType = typename CollectionT::iterator; IteratorType left = first; IteratorType leftEnd = mid; IteratorType temp = tmpCollection.begin(); auto const distance = std::distance(collection.begin(), first); std::advance(temp, distance); IteratorType right = mid; IteratorType rightEnd = last; // finger matching algo left and right while (left != leftEnd && right != rightEnd) { // this first if block here for equals is what does your duplicate removal magic if (*left == *right) { *temp++ = *left++; *temp++ = *right++; // ++right for non-duplicate } else if (*left < *right) { *temp++ = *left++; } else { *temp++ = *right++; } } // copy rest of left while (left != leftEnd) { *temp++ = *left++; } // copy rest of right while (right != rightEnd) { *temp++ = *right++; } collection = tmpCollection; } template void mergeSortCollection(CollectionT & collection, CollectionT & tmpCollection, typename CollectionT::iterator first, typename CollectionT::iterator last) { auto const distance = std::distance(first, last); if(distance > 1) { // get mid iterator auto mid = first; std::advance(mid, distance / 2); mergeSortCollection(collection, tmpCollection, first, mid); mergeSortCollection(collection, tmpCollection, mid, last); mergeCollection(collection, tmpCollection, first, mid, last); } } template void mergeSortCollection(CollectionT & collection) { CollectionT tmpCollection {collection}; mergeSortCollection(collection, tmpCollection, collection.begin(), collection.end()); } } 

一些测试代码：

 namespace { template auto printCollection = [](std::ostream& out, It const begin, It const end, std::string const & message = "") { using ValueType = typename std::iterator_traits::value_type; out << message; std::copy(begin, end, std::ostream_iterator(out, ", ")); out << std::endl; }; } TEST(Sort, MergeSortCollectionVector) { std::vector before = { 83, 86, 77, 15, 93, 35, 86, 92, 49, 21 }; std::vector original = before; std::vector after = { 15, 21, 35, 49, 77, 83, 86, 86, 92, 93 }; printCollection(std::cout, before.begin(), before.end(), "BEFORE sort: "); mergeSortCollection(before); printCollection(std::cout, before.begin(), before.end(), "AFTER sort: "); EXPECT_EQ(after, before); EXPECT_NE(original, before); } TEST(Sort, MergeSortCollectionList) { std::list before = { 83, 86, 77, 15, 93, 35, 86, 92, 49, 21 }; std::list original = before; std::list after = { 15, 21, 35, 49, 77, 83, 86, 86, 92, 93 }; printCollection(std::cout, before.begin(), before.end(), "BEFORE sort: "); mergeSortCollection(before); printCollection(std::cout, before.begin(), before.end(), "AFTER sort: "); EXPECT_EQ(after, before); EXPECT_NE(original, before); } 

正如其他人指出的那样，您需要对merge过程进行一些修改以满足您的需求。 下面是修改后的merge()函数供您参考（原文在这里 ）

 function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) < first(right) // <--- change from <= to < append first(left) to result left = rest(left) else if first(left) > first(right) append first(right) to result right = rest(right) else // <----- added case to remove duplicated items append first(right) to result left = rest(left) right = rest(right) end end while if length(left) > 0 append left to result else append right to result return result 

Answer 6

或者只是使用任何排序，当它完成时，扫描排序列表并删除重复的元素（它们自然会彼此相邻）