Ошибка тайм-аута в уведомлении о мошеннической деятельности HackerRank

Question

Я решаю эту проблему: Farudulent Уведомление о деятельности на HackerRank. Я закончил с моим кодом и работает, но он неэффективен также для очень больших входов.

Я не знаю, но после всех моих усилий, я могу дать хорошее решение проблемы среднего уровня, но это timeout error происходит каждый раз для очень больших входов. Я попытался оптимизировать мой код, и все равно получаю ошибки тайм-аута. Мои повестки дня для этого вопроса и предстоящие вопросы:

• Как поставить эффективность для очень больших входов. Какой интеллект ему необходим.
• Как достичь этого уровня. Что я должен подготовить для этого.
• Оптимизация кода

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

Мой алгоритм:

1. Для этой задачи мы должны перейти от incrementing variable i до len(givenArray)-d
2. Возьмите переменную для следующей сравниваемой переменной, в моем случае iterate - это переменная
3. Передайте значения в конкретный массив методу подсчета countFraud()
4. Добавить его в переменную count
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).

Не знаю, но этот код не передается для всех TC из-за Timeout Error. Там нет проблем в операционной части. Это просто с эффективностью кода.

Пример ввода ошибки тайм-аута:

200000 10000

Ссылка для ввода - Входные данные

Ожидаемый результат:

633

Я прочитал эту статью: Среда HackerRank , чтобы узнать о проблеме времени. Для Python / Python 3 это 10 секунд . Мой код определенно требует больше, чем это для values greater than 10^3 or 4.

Хотя мой код успешно прошел 3 TC. Пожалуйста, помогите. Спасибо:)

Answer 1

Поскольку никто на самом деле не дал мне ответ. Мне действительно нужно искать решение в таблице лидеров. Я нашел каждое решение слишком много, чтобы усвоить, только одно решение, чтобы быть хорошим.

Отказ от ответственности: Это некоторый продвинутый метод кодирования, поэтому вам необходимо лучше понять язык, прежде чем приступить к решению.

Алгоритм решения:

1. Это занимает два массива, один из которых имеет общее количество элементов массива, а другой - назовем его 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] в список D, используя PYTHON INSORT ALGORITHM в отсортированном виде
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 и Insort Algo ,Спасибо, и надеюсь, что это поможет кому-то в будущем.

Answer 2

Я потратил много времени на этот вопрос, и придумал новый собственный алгоритм, который также дает превышение предела времени (TLE), и прошел только три теста.

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstring>
using namespace std;
int maxlen=1,minlen=1,heapsize;
double median=0,ct=0;
void min_heapify(double arr[],int i)
{
    int l=(2*i);
    int r=(2*i+1);
    int smallest;
    if(l<=heapsize && arr[l]<arr[i])
    {
        smallest=l;
    }
    else
    {
        smallest=i;
    }
    if(r<=heapsize && arr[r]<arr[smallest])
    {
        smallest=r;
    }
    if(smallest==i)
        return;
    if(smallest!=i)
    {
        double swap=arr[i];
        arr[i]=arr[smallest];
        arr[smallest]=swap;
    }
    min_heapify(arr,smallest);
}
void max_heapify(double arr[], int i)
{
    int l=(2*i);
    int r=(2*i+1);
    int largest;
    if(l<=heapsize && arr[l]>arr[i])
    {
        largest=l;
    }
    else
    {
        largest=i;
    }
    if(r<=heapsize && arr[r]>arr[largest])
    {
        largest=r;
    }
    if(largest==i)
        return;
    if(largest!=i)
    {
        double swap=arr[i];
        arr[i]=arr[largest];
        arr[largest]=swap;
    }
    max_heapify(arr,largest);
}
void insert_valuein_minheap(double minh[], int i, double val)
{
    minh[i]=val;
    while(i>1 && minh[i/2]>minh[i])
    {
        double temp=minh[i/2];
        minh[i/2]=minh[i];
        minh[i]=temp;
        i=i/2;
    }
}
void insert_valuein_maxheap(double maxh[], int i, double val)
{
    maxh[i]=val;
    while(i>1 && maxh[i/2]<maxh[i])
    {
        double temp=maxh[i/2];
        maxh[i/2]=maxh[i];
        maxh[i]=temp;
        i=i/2;
    }
}
void insert_element(double maxh[], double minh[], double val, int size)
{
    if(val<=maxh[1])
    {
        maxlen+=1;
        insert_valuein_maxheap(maxh,maxlen,val);
    }
    else
    {
        minlen+=1;
        insert_valuein_minheap(minh,minlen,val);
    }
    if(maxlen==minlen)
    {
        median=(maxh[1]+minh[1])/2;
        ct=1;
        return;
    }
    if(maxlen<minlen)
    {
        maxlen+=1;
        insert_valuein_maxheap(maxh,maxlen,minh[1]);
        double temp=minh[1];
        minh[1]=minh[minlen];
        minh[minlen]=temp;
        minlen-=1;
        heapsize=minlen;
        min_heapify(minh,1);
    }
    else
    {
        minlen+=1;
        insert_valuein_minheap(minh,minlen,maxh[1]);
        double temp=maxh[1];
        maxh[1]=maxh[maxlen];
        maxh[maxlen]=temp;
        maxlen-=1;
        heapsize=maxlen;
        max_heapify(maxh,1);
    }
}
int main()
{
    int n,td,notif=0;
    cin>>n>>td;
    double array[n+1],maxh[n+1]={},minh[n+1]={};
    for(int i=1;i<=n;i++)
    {
        cin>>array[i];
    }
    double first,second;
    for(int i=1,j;i<=n-td;i++)
    {
        int count=2;
        first=array[i];
        second=array[i+1];
        if(first<=second)
        {
            maxh[1]=first;
            minh[1]=second;
        }
        else
        {
            maxh[1]=first;
            minh[1]=second;
        }
        maxlen=1;minlen=1;ct=0;
        for(j=i+2;count!=td;j++)
        {
            insert_element(maxh,minh,array[j],j);
            count++;
        }
        if(td%2!=0)
        {
            if(maxlen>minlen)
                median=maxh[1];
            else
                median=minh[1];
        }
        else if(ct==0)
        {
            median=(maxh[1]+minh[1])/2;
        }
        float nota=array[j];
        if(nota>=2*median)
        {
            notif++;
        }
    }
    cout<<notif<<endl;
}