合并排序删除重复项

Question

我试图通过合并排序对数组进行排序，并在排序时删除我认为相等的元素。我递归调用合并排序，然后合并。

到了这一点，我发现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];
    }

}

Answer 1

首先确保[start，mid]和[mid 1，end]中的元素已排序且唯一。否则，代码运行后将存在重复项。

Answer 2

您的合并从概念上改变了数组的长度。但是没有代码可以真正截断数据。我建议您返回长度（而不是void），并使用一些最终的后处理步骤将数据截断为最终长度，或者至少避免打印那些超过结束元素的数据。

Answer 3

C标准库的理念是使用能做好一件事的算法。最好遵循这种方法，因为它会导致更多可重用的代码。

例如，这里有一个mergesort草图，后面是对std::唯一的调用

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） 以实际擦除非唯一数据。