题目分析

1. 题目中给出我们n个字符串
2. 我们要按照字典序输出这n个字符串

方法一：库函数排序调用

• 实现思路
  • 我们先读取所有的字符串到words向量中
  • 调用sort函数对整个向量进行排序（字符串也支持排序，排序方式默认按照字典序的方式）
  • 输出排序后的结果即可

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    vector<string> words;
    while(cin >> s) {						// 输入所有的字符串到向量中
        words.push_back(s);
    }
    
    sort(words.begin(), words.end());		// 排序这个向量
    
    for(string word : words) {				// 顺序输出向量中排序后的结果
        cout << word << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(nlogn)O(nlogn)$，读取遍历所有字符串的时间代价为$O(n)O(n)$，排序的时间代价为$O(nlogn)O(nlogn)$
• 空间复杂度：$O(n)O(n)$，需要用线性级别的向量空间代价来装填所有的字符串

方法二：set集合结构

• 实现思路

  • 我们可以知道set结构可以内部以红黑树构造

  • 因此同样支持我们进行排序工作

  • 同时multiset支持重复元素的排序工作，因此我们采用multiset结构

  • 将输入字符串都加入multiset后，内部的红黑树结构会进行字典序排序

  • 最终输出multiset中的内容即可

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    multiset<string> ss;
    while(cin >> s) {				// 输入所有的字符串到multiset中
        ss.insert(s);
    }
    for(auto word : ss) {			// 输出所有排序好的结果
        cout << word << endl;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(nlogn)O(nlogn)$，读取遍历所有字符串的时间代价，set所使用的红黑树的构造和排序时间代价为$O(nlogn)O(nlogn)$成为了时间代价的决定因素
• 空间复杂度：$O(n)O(n)$，需要用线性级别的集合空间代价来装填所有的字符串