我如何针对大量输入字符串优化我的代码

Question

我在大学的编译器上通过了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最大值= 25978所以这些数字很大。有任何想法吗？任务是检查单词是否是字谜。

Answer 1

您不必对字符串进行排序即可检查它们是否为字谜。字谜的顺序无关紧要，那么为什么要对它们排序呢？

最多排序为O(n log n)，而简单地计算字符的频率为O(n)。要计算字符，您可以使用std::unordered_map，或者如果不允许，则使用计数器数组。遍历字符串以计算每个字符的出现次数，然后比较计数器数组。