欺诈活动通知问题降低时间复杂性

Question

我试图从HackerRank解决Python3中的排序问题：https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem

这个问题需要在运行的基础上找到每个子列表的中值。在

由于超时终止，我的代码可以用于示例测试用例，但不完全适用于实际测试用例。我怀疑每次使用sort（）查找中间值会导致时间延迟。在

如何改进我的代码？在

def activityNotifications(expenditure, d):
    totalDays = len(expenditure)
    notified = 0

    for x in range(d, totalDays):
        check = expenditure[x-d:x]
        check.sort()

        if d % 2 == 0:
            median = (check[int(d/2)] + check[int((d-2)/2)])/2
        else:
            median = check[int((d-1)/2)]

        if expenditure[x] >= median * 2:
            notified += 1

    return notified

Answer 1

为了在每次迭代中找到一个中间值，您需要对子数组进行排序。它不是真正有效的，尤其是当d不小的时候。每次迭代的时间复杂度是O(dlog(d))。在

要找到中值，我们需要一个排序数组，但不需要sort()方法。如果我们注意到每个expenditure[i]都在[0;200]范围内，那么计数排序在这里听起来是个好主意。基本上，我们用counts[i]来计算每个数i的频率。为了得到一个排序数组，我们只需要迭代j: counts[j] > 0。在

因此，如果counts为每个长度d（区间[i; i + d)）的间隔保持expenditure个数的频率，我们最多可以通过检查counts中的201个数来找到一个中值（有关详细信息，请参阅代码）。移动到下一个间隔[i+1; i+d+1)需要将数字i的频率递减为counts[i] ，而增加i+d的频率。 这种方法需要O(n*201)时间和O(201)空间复杂性。在

现在，请参见下面的代码：

def activityNotifications(expenditure, d):
    totalDays = len(expenditure)
    counts = [0] * 201
    notifications = 0

    for i in range(totalDays):
        # now we have enough data to check if there was any fraudulent activity
        if i >= d:
            # let's count frequencies of numbers in range [i - d; i)
            current_num_of_numbers = 0
            prev_number = -1
            for j in range(201):
                if counts[j] > 0:
                    current_num_of_numbers += counts[j]
                    # now we can determine the median because we have enough numbers
                    if d < (2 * current_num_of_numbers):
                        if (d % 2 == 0) and (current_num_of_numbers - counts[j] == d / 2):
                            median = (prev_number + j) / 2
                        else:
                            median = j

                        # if the condition is met then send a notification
                        if expenditure[i] >= (median * 2):
                            notifications += 1
                            break
                    prev_number = j
                counts[expenditure[j - d]] -= 1
        counts[expenditure[i]] += 1

    return notifications