题目分析

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

方法一：库函数排序调用

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

alt

#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)，需要用线性级别的集合空间代价来装填所有的字符串