Как я могу оптимизировать мой код для большого количества строк на входе - PullRequest
Новая
       7

Как я могу оптимизировать мой код для большого количества строк на входе

0 голосов
/ 30 марта 2020

Я сдал 4 теста на мой университетский компилятор, и проблема в 5-м. Ограничение по времени составляет 1 секунду для каждого теста. Как я могу оптимизировать этот код, может быть, есть лучший вариант для сортировки, если я сравниваю строки? Мой код: 

#include <iostream>
#include <string.h>

using namespace std;

void qsort(string &tab, int min, int max)
{
    if(min<max)
    {
        int min_min = min;
        for(int i=min+1;i<=max;i++)
        {
            if(tab[i]<tab[min])
            {
                swap(tab[++min_min],tab[i]);
            }
        }
        swap(tab[min],tab[min_min]);
        qsort(tab,min,min_min-1);
        qsort(tab,min_min+1,max);

    }
}
bool sprawdz(string tab,string tab2)
{
    for(int i=0;i<tab.length();i++)
    {
        if(tab[i]!=tab2[i])
        {
            return false;
            break;
        }
    }
    return true;
}

int main()
{
    string tablica1, tablica2;
    int ile;

    scanf("%d",&ile);
    for(int i=0;i<ile;i++)
    {
        cin>>tablica1>>tablica2;
        qsort(tablica1,0,tablica1.length()-1);
        qsort(tablica2,0,tablica2.length()-1);

        if(tablica1==tablica2)
        {
            printf("TAK\n");
        }
        else
        {
            printf("NIE\n");
        }


    }

    return 0;
}

Выводится только информация min = 25177 max = 25978, поэтому эти цифры довольно велики. Любые идеи? Задача - проверить, являются ли слова анаграммами.

1 Ответ

1 голос
/ 30 марта 2020

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

Мой любимый совет: оптимальный способ сделать что-то - это не делать;)

Вам не нужно сортировать строки, чтобы проверить, являются ли они анаграммами. Для анаграмм порядок не имеет значения, так зачем их сортировать?

Сортировка обычно O(n log n), в то время как простой подсчет частоты символов O(n). Для подсчета символов вы можете использовать std::unordered_map, или, если это не разрешено, использовать массив счетчиков. Пройдите по строкам, чтобы сосчитать вхождения каждого персонажа, затем сравните массивы счетчиков.

PS: Вы также должны проверить, одинаков ли размер строк, прежде чем применять какие-либо дальнейшие логи c.

...