如何使用合并排序来删除重复？ [英] How do I use merge sort to delete duplicates?

问题描述

我用递归归并排序进行排序的链接列表，但在合并过程中的排序，我想删除重复。任何人在如何做到这一点的见解？

I use recursive merge sort for sorting a link list, but during the merge sort I would like to delete duplicates. Anyone has insight in how to accomplish this?

我使用C code。

推荐答案

在合并排序，你需要两个（或更多）已排序列表重复应用以下规则：

In merge sort you take two (or more) already-sorted lists repeatedly apply the following rules:

• 找到的较小/最少的每个输入列表的顶部的物品，选择任何最低的项目，如果有平局
• 从名单中删除该项目
• 将其添加到您的输出列表

要删除重复，你只需修改规则非常轻微：

To remove duplicates, you simply modify the rules very slightly:

• 找到的较小/最少的每个输入列表的顶部的物品，选择任何最低的项目，如果有平局
• 从名单中删除该项目
• 如果是一样的，你添加到您的输出列表中的最后一个项目，把它扔掉
• 否则，将其添加到您的输出列表

这将确保没有两个连续的项的输出列表上是相同的，并在它的项是在顺序，这是你是什么之后

This will ensure that no two consecutive items on your output list are the same, and that the items in it are in order, which is what you were after.

这篇关于如何使用合并排序来删除重复？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！