python - 欺诈事件通知中出现超时错误 HackerRank

Question

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

I don't know but after all my efforts, I am able to give out good solution to a problem of a MEDIUM LEVEL but this timeout error happens every time for very large inputs. I have tried optimizing my code and still I get timeout errors. My agendas for this question and upcoming questions are:

• How to put efficiency for very large inputs. What kind of intellect it requires.
• How to reach to that level. What should I prepare for this.
• Code optimization

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

我的算法:

1. For this problem we must go from incrementing variable i till len(givenArray)-d
2. Take a variable for the next variable to be compared, my case iterate is the variable
3. Pass the values to the particular array to the method for counting countFraud()
4. Add it to the count variable
5. Increment iterate variable

代码:

# 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)。

我不知道，但由于超时错误，此代码未针对所有 TC 提交。操作部分没有问题。这只是与代码的效率有关。

超时错误输入示例:

200000 10000

输入链接 - Input Data

预期输出:

633

我读过这篇文章:HackerRank Environment了解时间问题。对于Python/Python 3，它是10秒。我的代码肯定比 值大于 10^3 或 4 需要更多的时间。

我的代码已成功通过 3 个 TC。请帮忙。谢谢:)

Answer 1

因为没有人真正给我答案。我真的必须在排行榜上寻找解决方案。我发现每种解决方案都难以消化，只有一种解决方案才是好的解决方案。

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

解决方案的算法:

1. This takes two arrays, one is t having total number of array elem and other one let us name it as listD just the first d elements in the sorted manner
2. A function to return the median value with the list containing first d elements
3. With the loop starting from the d and going till n-1, if t[i] >= 2*median(): increment var noti
4. Remove the first element from the listD using PYTHON BISECT ALGORITHM and add it the t[i] to the listD using PYTHON INSORT ALGORITHM in sorted manner
5. Return noti

代码:

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)

这里，我们使用了BISECT和INSORT，它们的作用基本上是，返回要添加的元素的位置，并返回添加后的排序列表元素。这样就减少了一次又一次对数组排序的麻烦，从而降低了时间复杂度并解决了所有测试用例。

您可以在这里阅读:Python Bisect and Insort Algo 。谢谢，并希望它对将来的人有所帮助。