Время ожидания уведомления о мошеннических действиях / ошибка времени выполнения - PullRequest
Новая
       67

Время ожидания уведомления о мошеннических действиях / ошибка времени выполнения

0 голосов
/ 01 мая 2020

Я пытаюсь решить эту проблему на Hackerrank:

В Национальном банке HackerLand действует простая политика предупреждения клиентов о возможной мошеннической деятельности аккаунта. Если сумма, потраченная клиентом в определенный день, больше или равна средним расходам клиента за последние дни, они отправляют клиенту уведомление о возможном мошенничестве. Банк не отправляет клиенту никаких уведомлений, пока у него не будет хотя бы того конечного числа данных транзакций за предыдущие дни.

С учетом количества конечных дней $ d $ и общих ежедневных расходов клиента за период дней, найдите и напечатайте, сколько раз клиент получит уведомление за все дни.

Например, $ d = 3 $ и $ затрат = = [10,20,30,40,50] $. В первые три дня они просто собирают данные о расходах. В день 4 $ у нас есть конечные расходы $ [10,20,30] $. Медиана составляет 20 долларов, а дневные расходы - 4 доллара. Поскольку $ 40 \ geq 2 \ times 20 $, будет уведомление. На следующий день наши конечные расходы составляют $ [20,30,40] $, а расходы - $ 5- $. Это меньше, чем $ 2 \ умножить на 30 $, поэтому уведомление не будет отправлено. За отчетный период было отправлено одно уведомление.

Моя первая попытка состояла в том, чтобы взять первые d элементов, сохранить их в массиве и использовать сортировку для амортизированной стоимости $ O (d \ log (d)) $. Затем с каждой итерацией я удаляю наименее проиндексированный элемент и добавляю расходы на следующие дни, где он принадлежит в списке, в среднем за O (d) времени. Однако в скрытых тестовых примерах я получаю ошибку времени выполнения, которая, как я подозреваю, связана с тем, что в этих случаях она очень велика. В одном примере $ n = 200000 $ и $ d = 10000 $.

Моя вторая попытка заключалась в использовании медианы медиан или алгоритма быстрого выбора, который в среднем должен стоить O (d), но я получать тайм-ауты. Я не знаю, что делать

Вот мой код для второй попытки: 

#!/bin/python

import math
import os
import random
import re
import sys

# Complete the activityNotifications function below.
def quickselect(List, index):
    if len(List) == 1:
        assert index == 0
        return List[0]
    pivot = random.choice(List)
    lows=[];
    highs=[];
    pivots=[];
    for el in List:
        if el<pivot:
            lows.append(el);
        elif el >pivot:
            highs.append(el);
        else:
            pivots.append(el);
    if index < len(lows):
        return quickselect(lows, index)
    elif index < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quickselect(highs, index - len(lows) - len(pivots));

def quickselectmedian(List):
    if len(List)%2 == 1:
        return quickselect(List,len(List)/2);
    else: 
        return 0.5*(quickselect(List,len(List)/2-1)+quickselect(List,len(List)/2));

def activityNotifications(expenditure, d):
    r=len(expenditure);
    numnotif=0; 
    for j in range(d,r):
        med = quickselectmedian(expenditure[j-d:j]);
        if 2*med <= expenditure[j]:
            numnotif+=1; 
    return numnotif;

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nd = raw_input().split()

    n = int(nd[0])

    d = int(nd[1])

    expenditure = map(int, raw_input().rstrip().split())

    result = activityNotifications(expenditure, d)

    fptr.write(str(result) + '\n')

    fptr.close()
...