1

给你一个数组 A，包含 n 个 2010 年奥运会门票的请求。该数组按请求的时间排序，因此 A(1) 是第一个到达的，A(2) 是第二个到达的，依此类推。每个请求包含一个十位数的电话号码。为了公平起见，奥运会组织者制定了一个规则，即每个电话号码只能有一个请求。已经注意到数组 A 包含来自某些电话号码的多个请求。编写一个 O(nlogn) 时间分治算法，从 A 中删除来自同一电话号码的所有请求，除了第一个收到的请求。最终输出应该是数组 A，其中包含来自唯一电话号码的 m<=n 个请求。此外，A 中的请求应保持与删除重复项之前相同的顺序。

如果数组按电话号码排序，我知道如何做到这一点，但是我看不出当数组按请求时间排序时怎么可能。

4

1 回答 1

8

对归并排序的简单修改就可以解决问题。归并排序是 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 与自定义比较功能一起使用，该功能可以比较电话号码和日期/时间。然后对排序后的数组进行最后一次传递以删除重复项。

快速排序和合并排序都被认为是分而治之的算法。

于 2013-10-29T14:51:29.427 回答