Не проходит один из тестов.Нужна оптимизация скорости выполнения кода на Си

Question

Задача: Дан массив. Размер не превышает 10000 элементов. Его вводят через стандартный поток ввода. Сначала вводят длину массива (N) - натуральное число. Затем следует N целых чисел (не выходят за диапазоны int) - элементы массива. Найдите и распечатайте в стандартный поток вывода единственное число:

Количество элементов массива, каждый из которых встречается в массиве не более 3-х раз.

Напишите программу на языке Си.

Последний тест выполняется долго и тест выводит "тайм-аут".


int main() {
    int n, arr[10000] = {0};

    scanf("%d", &n);

    for(int i = 0; i < n; i++) {
        
        scanf("%d", &arr[i]);
    }

    int max = -1, min = 10000;

    for(int i = 0; i < n; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }
        if(arr[i] < min) {
            min = arr[i];
        }
    }

    int result = 0;

    for(int i = min; i <= max; i++) {
        int rep = 0;
        for(int j = 0; j < n; j++) {
            if(arr[j] == i) {
                rep++;
            }
        }
        if(rep > 0 && rep <= 3) {
            result++;
        }
    }

    printf("%d\n", result);

    return 0;
}

Прикрепляю входные данные. Заранее спасибо. Входные данные

Answer 1

У вас подход странный — идти не от массива, а от значений. Если в данные внести какие-нибудь 1000000000 и -1000000000, то получается страшное...

Вот, даже если не стремиться к O(N log N), а ограничиться O(N^2)...

struct
{
    int a;
    int c;
} arr[10000];

int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &arr[i].a);

    int result = 0;

    for(int i = 0; i < n; i++)
    {
        if (arr[i].c) continue;

        arr[i].c = 1;
        for(int j = i+1; j < n; j++)
            if(arr[j].a == arr[i].a) arr[j].c = ++arr[i].c;
        if (arr[i].c >= 1 && arr[i].c <= 3) result++;
    }

    printf("%d\n", result);
}

Этого при ваших 10000 элементов вполне должно хватать (ваш удвоенный (до 10000 элементов) массив ваша программа на моей машине берет за 180 мс, моя за 30 мс, но главное, что моя не зависит от значений в массиве.

Главное — надо не перебирать (в пределе) весь диапазон int в 4 с лишним миллиарда, а идти от массива.

O(N log N) можно получить, отсортировав за O(N log N), а потом проходя по массиву и проверяя количество одинаковых подряд.

int cmp(const void * a, const void * b)
{
    return *(int*)a < *(int*)b ? -1 : *(int*)a > *(int*)b
}

int main()
{
    int arr[10000] = {0};
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    qsort(arr,n,sizeof(int),cmp);

    int result = 0;
    for(int i = 0; i < n; i++)
    {
        int cnt = 1;
        if (i < n-1 && arr[i] == arr[i+1])
        {
            int a = arr[i++];
            while(i < n && arr[i] == a)
            {
                ++i;
                ++cnt;
            }
            if (i < n) --i;
        }
        if (cnt <= 3) result++;
    }

    printf("%d\n", result);
}

Эта у меня работает порядка 10 мс, но даже приведенная первой программа справляется быстро — очень уж небольшое у вас количество данных.

БЛОГ НА HUSL

Не проходит один из тестов.Нужна оптимизация скорости выполнения кода на Си

Ответы (1 шт):