arrays - 在 O(nlogn) 时间内使用分而治之从数组中删除重复项

Question

给你一个包含 n 个 2010 年奥运会门票请求的数组 A。该数组按请求时间排序，因此 A(1) 是第一个到达的，A(2) 是第二个到达的，依此类推。每个请求都包含一个十位数的电话号码。为了公平起见，奥林匹克组织者规定每个电话号码只能提出一个请求。注意到数组 A 包含来自某些电话号码的多个请求。编写一个时间复杂度为 O(nlogn) 的分治算法，从 A 中删除除第一个收到的同一电话号码之外的所有请求。最终输出应该是数组 A，其中包含来自唯一电话号码的 m<=n 个请求。此外，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 和 Mergesort 都被认为是分而治之的算法。