题解 | #简单错误记录#

题目分析

1. 题目给出我们若干文件路径和文件对应的行数
2. 题目规定我们只取每个文件的文件名信息（去除绝对路信息），并截取末尾16位（如果不足16位则不需要截取）
3. 因此会碰到不同绝对路径可能被认定为同一个错误记录的情况，这是允许的，并且对于这种情况只统计第一次的错误信息
4. 最终需要返回最后8个错误记录

方法一：列表方式

• 实现思路
  • 对于每一条输入，我们将其提取成最后要输出的格式字符串error，其中也做好了对末16位的处理
  • 我们将error按照顺序装填到errors列表中，并同时判断处理同一个错误记录出现的情况
  • 同时统计次数
  • 最终输出后8位内容即可

import sys
errors = []
count = []

for line in sys.stdin:
    error = line.split()[0].split("\\")[-1][-16:] + " " + line.split()[1]		# 提炼出最终结果的格式字符串
    if error not in errors:														# 判断是否出现过error
        errors.append(error)													# 添加到列表末尾
        count.append(1)															# 计数为1
    else:
        count[errors.index(error)] += 1											# 否则在原来的错误记录位置更新数量
    
for i in range(len(errors[-8:])):
    print(errors[-8:][i], count[-8:][i])										# 最终统计后八位即可

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，读取n条记录，并且对每条记录都要执行查找工作，最终是两者乘积的时间代价
• 空间复杂度：$O(n)O(n)$，存储每一条记录所申请的额外空间

方法二：字典方式

• 实现思路

  • 由于字典是按照哈希表的原理处理的，因此在查找是否出现过某个错误时间代价会优化成常量级别

  • 这样实现了在时间代价上的优化

import sys
import collections

# 用字典的方式有哈希的实现效果
errors = collections.defaultdict(int)    # 必须用int类型参数来初始化默认字典中的元素value为0
result = []

for line in sys.stdin:
    path, row = line.strip().split()	 # 切割路径和行数信息
    path = path.split("\\")[-1]
    if len(path) > 16:
        path = path[-16:]
    error = " ".join([path, row])		 # 整理成最终的结果格式
    errors[error] += 1					 # 直接在字典的访问方式中统计出现次数
    if errors[error] == 1:               # 只记录该error第一次出现时，放到result的列表中
        result.append(error)
    
for r in result[-8:]:
    print(r, errors[r])

复杂度分析

• 时间复杂度：$O(n)O(n)$，只需要遍历所有的信息的时间开销，查找的时间开销被剩下来了
• 空间复杂度：$O(n)O(n)$，存储每一条记录所申请的额外空间