string - 在 C++ 中按字典顺序对字符串进行排序

Question

我是编程新手。我刚刚学习了 C++ 中的字符串。

我有N个字符串，我想按字典顺序对它们进行排序。(字典顺序)

怎么样，我可以这样做吗，因为 N 很大 1 <= N <= 1e5每个字符串的大小为 1 <= |s| <= 1000 .

此外，该字符串仅由小英文字母组成。

我已经找到了一种对它们进行排序的方法，但测试用例很严格并且给出了 TLE。

有没有更好的方法来解决这个问题。请帮忙。

Answer 1

是的，有两种方法。

1. 使用哈希。

如何使用？

• 创建一个大小为 26 的简单整数数组 (hash[])。考虑到您的字符串仅由小字母组成，它的每个索引都表示一个字母。
• 将数组初始化为零。
• 现在遍历字符串，对于字符串中出现的每个字母，在 hash[] 中将其频率加一。例如，如果 'a' 出现在字符串中，则 hash[0] = hash[0] + 1;
• 完成上述步骤后。您将获得哈希中所有字符的频率。
• 现在遍历您的 hash[]，并为每个索引 i 打印所有字符，直到 hash[i] 变为零。这是因为，当您想要按字典顺序对字符串进行排序时，最好的方法是打印字符串中存在的所有“a”，然后打印所有“b”等。
• 上述方法的时间复杂度为O(n*2s)。
• 以下是程序

int hash[26]={0};
for( int i = 0 ; i < s.length() ; i++ ) // s.length() returns string length
{
   hash[s[i]-97] += 1; // s[i] - 97 actually returns index for the character
}
char ch;
for( int i = 0 ; i < 26 ; i++ )
{
   ch = i+97; // making the character required
   while(hash[i]) { cout << ch; hash[i] -= 1; } // printing it its frequency times
}

使用nlog(n)排序

• 在 C++ 中，您还可以使用 sort() 函数对字符串进行排序。

怎么做？

• 只需编写 sort( s.begin() , s.end() ) ;
• 该方法的复杂度为 O(n*|s|log(|s|))
• 代码如下

string s;
cin >> s;
sort( s.begin(); s.end() );
cout << s << endl;