180人的大班级中找出所有生日相同的学生

在一个有180人的大班级中,存在两个人生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。

时间限制:1000
内存限制:65536
输入
第一行为整数n,表示有n个学生,n ≤ 180。此后每行包含一个字符串和两个整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月(1 ≤ m ≤ 12)日(1 ≤ d ≤ 31)。名字、月、日之间用一个空格分隔
输出
每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字、名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。 对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如没有生日相同的学生,输出”None”
样例输入
6
Avril 3 2
Candy 4 5
Tim 3 2
Sufia 4 5
Lagrange 4 5
Bill 3 2
样例输出
3 2 Tim Bill Avril
4 5 Candy Sufia Lagrange

https://ask.csdn.net/questions/7997160

【以下回答由 GPT 生成】

解决方案:
1. 创建一个Map,键为生日(月+日),值为一个vector,存储在该生日出生的学生名字。
2. 遍历每个学生的信息,将学生的名字添加到对应生日的vector中。
3. 遍历Map中的每一对键值对,按照日期从小到大的顺序输出生日相同的学生名字。
注意:为了排序和输出的方便,需要使用一个自定义的比较函数来对学生名字进行排序。

以下是C++的代码实现:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

// 自定义比较函数,用于对学生名字进行排序
bool compare(string a, string b) {
    if (a.length() != b.length()) {
        return a.length() < b.length();
    } else {
        return a < b;
    }
}

int main() {
    int n;
    cin >> n;

    map<string, vector<string>> birthdayMap;

    for (int i = 0; i < n; i++) {
        string name;
        int month, day;
        cin >> name >> month >> day;

        string birthday = to_string(month) + " " + to_string(day);

        birthdayMap[birthday].push_back(name);
    }

    bool hasSameBirthday = false;

    for (auto it = birthdayMap.begin(); it != birthdayMap.end(); it++) {
        if (it->second.size() > 1) {
            hasSameBirthday = true;

            // 对学生名字按照自定义比较函数进行排序
            sort(it->second.begin(), it->second.end(), compare);

            // 输出生日相同的学生名字
            cout << it->first << " ";
            for (int i = 0; i < it->second.size(); i++) {
                cout << it->second[i] << " ";
            }
            cout << endl;
        }
    }

    if (!hasSameBirthday) {
        cout << "None" << endl;
    }

    return 0;
}

复杂度分析: - 时间复杂度:O(nlogn),其中n为学生人数。需要遍历每个学生的信息,将学生名字添加到Map中,而对Map中的键值对按日期进行排序需要O(nlogn)的时间复杂度。 - 空间复杂度:O(n),需要额外的空间来存储Map和每个生日对应的学生名字。



【相关推荐】



如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^