手机来电记录最少保留数量算法：年份恢复

{"title": "【问题描述】\n有一部手机记录了一些来电信息。每条信息包含日期（月和日）、时间（小时和分钟）以及号码。能记录的来电数量是有限的。你发现这个限制数量很快就要达到了，因此准备删除一些来电记录。在选择删除记录的时候你需要考虑下面两个限制：\n\t1. 有一些重要的来电记录你要保留。\n\t2. 你想让留下来的这些记录能够恢复来电的年份（注意，这是手机没有记录的）。恢复的方法在下面描述。\n计算出在满足上述限制的条件下，最少需要保留的来电记录数量。\n年份恢复方法：给定一系列的来电时间戳（内容包含月、日、小时、分钟），你按照如下方式推导年份。\n\t1）最后一个来电是今年的。\n\t2）通过比较最后来电和前一个来电的时间戳和，如果，你假设两个电话是同一年的，反之是前一年的。\n\t3）不断向前回溯得到所有电话的年份。\n这个方法并不一定对，但你可以假设输入中来电记录的年份按照这个规则恢复是正确的，并且经过删除之后的日志文件能够恢复的结果要和输入一致。\n提示：因为使用的一个手机软件错误，没有一个来电记录的日期是2月29。\n【输入形式】\n输入包含1组用例。每个测试用例第一行包含一个整数。接下来的行，每行有一条来电记录。每条来电记录的格式为mm:dd:HH:MM number ±。它表示：mm月dd日HH时MM分来电，号码是number(1-16位)，+表示必须保存的电话（对应前述限制条件1），-表示其他的来电。\n【输出形式】\n对每个测试用例，输出最小数字，表示需要保存的最少来电记录数量。保存的来电需要满足前面的两条限制条件。\n【样例输入】\n7\n12:31:23:59 0123456789012345 +\n07:21:19:00 1337 -\n01:01:00:00 0987654321 -\n07:21:14:00 1337 -\n11:11:11:11 11111111111 +\n01:01:00:00 0123456789 +\n01:01:00:00 0987654321 -\n\n【样例输出】\n\n6\n根据问以上题描述，给出问题的求解程序在运行时的输入形式和输出形式要求描述、以及一个样例输入和输出的提示，给出一个算法，设计求解这个问题的算法，将算法和对算法的分析写出来，并在作答区将算法以伪代码的形式给出，并分析算法的时间和空间复杂性。给出相应的c语言代码，以此给一个报告。内容：【算法描述】\n1. 首先，将所有需要保留的来电记录保存到一个列表中。\n2. 对于列表中的每条记录，按照时间戳的先后顺序进行排序。\n3. 从列表中的第一条记录开始，通过比较当前记录和前一条记录的时间戳，判断是否为同一年的来电记录。\n4. 如果是同一年的来电记录，则将当前记录加入到最终保留的来电记录列表中。\n5. 如果不是同一年的来电记录，则将当前记录的时间戳修改为前一年的时间戳，并将其加入到最终保留的来电记录列表中。\n6. 继续遍历列表中的下一条记录，重复步骤3-5，直到遍历完所有记录。\n7. 最终保留的来电记录数量即为最少需要保留的来电记录数量。\n\n【伪代码】\n1. 定义一个列表saved_records，用于保存需要保留的来电记录。\n2. 将输入的来电记录按照时间戳的先后顺序进行排序，得到有序列表sorted_records。\n3. 将sorted_records的第一条记录加入到saved_records中。\n4. 对于sorted_records中的每条记录record（从第二条开始）：\n\t1) 获取前一条记录pre_record。\n\t2) 如果record和pre_record的时间戳是同一年的，则将record加入到saved_records中。\n\t3) 如果record和pre_record的时间戳不是同一年的，则将record的时间戳修改为前一年的时间戳，并将record加入到saved_records中。\n5. 输出saved_records的长度，即为最少需要保留的来电记录数量。\n\n【算法分析】\n1. 时间复杂度：排序需要O(nlogn)的时间，遍历列表需要O(n)的时间，总时间复杂度为O(nlogn)。\n2. 空间复杂度：需要保存最终保留的来电记录，空间复杂度为O(n)。\n\n【C语言代码】\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\n// 结构体定义来电记录\ntypedef struct {\n\tint month;\n\tint day;\n\tint hour;\n\tint minute;\n\tchar number[17];\n\tchar sign;\n} CallRecord;\n\n// 比较函数，用于排序\nint compare(const void *a, const void *b) {\n\tCallRecord *recordA = (CallRecord *)a;\n\tCallRecord *recordB = (CallRecord *)b;\n\n\tif (recordA->month == recordB->month) {\n\t\tif (recordA->day == recordB->day) {\n\t\t\tif (recordA->hour == recordB->hour) {\n\t\t\t\treturn recordA->minute - recordB->minute;\n\t\t\t}\n\t\t\treturn recordA->hour - recordB->hour;\n\t\t}\n\t\treturn recordA->day - recordB->day;\n\t}\n\treturn recordA->month - recordB->month;\n}\n\n// 判断两条记录是否是同一年的\nint isSameYear(CallRecord recordA, CallRecord recordB) {\n\tif (recordA.month > recordB.month) {\n\t\treturn 1;\n\t} else if (recordA.month < recordB.month) {\n\t\treturn 0;\n\t} else {\n\t\tif (recordA.day > recordB.day) {\n\t\t\treturn 1;\n\t\t} else if (recordA.day < recordB.day) {\n\t\t\treturn 0;\n\t\t} else {\n\t\t\tif (recordA.hour > recordB.hour) {\n\t\t\t\treturn 1;\n\t\t\t} else if (recordA.hour < recordB.hour) {\n\t\t\t\treturn 0;\n\t\t\t} else {\n\t\t\t\tif (recordA.minute >= recordB.minute) {\n\t\t\t\t\treturn 1;\n\t\t\t\t} else {\n\t\t\t\t\treturn 0;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n}\n\n// 将记录的时间戳修改为前一年的时间戳\nvoid modifyYear(CallRecord *record) {\n\trecord->month--;\n\trecord->day--;\n\trecord->hour--;\n\trecord->minute--;\n}\n\nint main() {\n\tint n;\n\tscanf("%d", &n);\n\n\tCallRecord *records = (CallRecord *)malloc(n * sizeof(CallRecord));\n\tfor (int i = 0; i < n; i++) {\n\t\tscanf("%d:%d:%d:%d %s %c", &records[i].month, &records[i].day, &records[i].hour, &records[i].minute, records[i].number, &records[i].sign);\n\t}\n\n\tqsort(records, n, sizeof(CallRecord), compare);\n\n\tint saved_count = 1;\n\tfor (int i = 1; i < n; i++) {\n\t\tif (isSameYear(records[i], records[i - 1])) {\n\t\t\tsaved_count++;\n\t\t} else {\n\t\t\tmodifyYear(&records[i]);\n\t\t\tsaved_count++;\n\t\t}\n\t}\n\n\tprintf("%d\n", saved_count);\n\n\tfree(records);\n\treturn 0;\n}