欺诈活动通知中的超时错误 HackerRank

Question

我正在解决这个问题：HackerRank上的 Farudulent Activity Notification。我已经完成了我的代码并且正在工作，但是对于非常大的输入，它也效率低下。

我不知道，但经过我所有的努力，我能够为中等级别的问题提供很好的解决方案，但是timeout error对于非常大的输入，每次都会发生这种情况。我尝试优化我的代码，但仍然出现超时错误。我对这个问题和即将提出的问题的议程是：

• 如何为非常大的输入提高效率。它需要什么样的智慧。
• 如何达到那个水平。我应该为此准备什么。
• 代码优化

我乐于学习，我真的很想学习如何编写更高级和优化的代码来让自己变得更好。我愿意努力工作。

我的算法：

1. 对于这个问题，我们必须从incrementing variable i直到len(givenArray)-d
2. 取一个变量作为下一个要比较iterate的变量，我的情况是变量
3. 将特定数组的值传递给计数方法 countFraud()
4. 将其添加到计数变量
5. 递增迭代变量

代码：

# this is for counting the trailing array
def countFraud(arr, nextNum):
    count = 0
    median = 0.0
    d = len(arr)
    #for calculating the median correctly
    arr.sort()
    if d%2 != 0:
        median = arr[int(d/2)]
    else:
        n = int(d/2)
        median = (arr[n] + arr[n-1]) / 2

    #now the opeartion for count from the array
    if nextNum >= 2*median: count += 1
    return count

# Complete the activityNotifications function below.
def activityNotifications(expenditure, d):
    count = 0
    iterate = d
    # it will go upto the len of array - d, so that it will go upto the d length
    # leaving the last element everytime for the comparision
    for i in range(len(expenditure)-d):
        count += countFraud(expenditure[i:iterate], expenditure[iterate])
        iterate += 1
    return count

现在之前我做了两个循环，将项目添加到new_array并将其传递给countFraud(). 但现在我已经优化它并使它有点像O(N).

我不知道，但由于Timeout Error. 操作部分没有问题。它只是与代码的效率有关。

超时错误输入示例：

200000 10000

输入链接 -输入数据

预期输出：

633

我已经阅读了这篇文章：HackerRank Environment以了解计时问题。对于Python/Python 3，它是10 秒。我的代码肯定比values greater than 10^3 or 4.

不过，我的代码已成功通过了 3 个 TC。请帮忙。谢谢你 ：）

Answer 1

因为实际上没有人给我答案。我真的必须在排行榜中寻找解决方案。我发现每一个解决方案都难以吸收，只有一个解决方案才是好的解决方案。

免责声明：这是一些高级编码技术，因此在继续解决方案之前，您需要更好地理解该语言。

解决方案的算法：

1. 这需要两个阵列，一个是具有阵列ELEM和其他一个的总数目T让我们将其命名为listD只是first d elements在排序方式
2. 返回包含前 d 个元素的列表的中值的函数
3. 循环从 d 开始直到 n-1， if t[i] >= 2*median(): increment var noti
4. 从listD使用 PYTHON BISECT ALGORITHM 中删除第一个元素，并t[i]使用 PYTHON INSORT ALGORITHM 以排序方式将其添加到 listD
5. 退货通知

代码：

from bisect import bisect_left, insort_left

n, d = map(int, input().split())
t = list(map(int, input().split()))
noti = 0

listD = sorted(t[:d])

def median():
  return listD[d//2] if d%2 == 1 else ((listD[d//2] + listD[d//2-1])/2)

for i in range(d,n):
  if t[i] >= 2*median(): noti += 1
  del listD[bisect_left(listD, t[i-d])]
  insort_left(listD, t[i])
print(noti)

在这里，我们使用了BISECTand INSORT，他们所做的基本上就是返回要添加元素的位置，并返回添加元素后的排序列表。因此减少了一次又一次排序数组的头痛，从而降低了时间复杂度并解决了所有测试用例。

你可以在这里阅读它：Python Bisect and Insort Algo。谢谢，希望它对未来有所帮助。