每日一题——Python代码实现PAT乙级1082 射击比赛（举一反三+思想解读+逐步优化）四千字好文

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

我的写法

代码分析

代码步骤

时间复杂度分析

空间复杂度分析

总结

我要更强

时间复杂度分析

空间复杂度分析

总结

哲学和编程思想

KISS原则（Keep It Simple, Stupid）：

YAGNI原则（You Ain't Gonna Need It）：

效率优化：

数据结构的选择：

函数式编程思想：

抽象和模块化：

实用主义：

举一反三

题目链接：https://pintia.cn/problem-sets/994805260223102976/exam/problems/type/7?problemSetProblemId=994805260990660608&page=0

我的写法

n=int(input())
player_scores=[]
for i in range(n):
    player_score=input().split()
    player_score[1]=int(player_score[1])
    player_score[2]=int(player_score[2])
    player_scores.append([player_score[0],player_score[1]**2+player_score[2]**2])
    
ranking=sorted(player_scores,key=lambda x: x[1])
print(f"{ranking[0][0]} {ranking[-1][0]}")

代码分析

这段代码实现了射击比赛的排名功能，根据输入的运动员编号和射击坐标，计算每个运动员的得分（距离靶心的平方和），然后对运动员进行排序，最后输出得分最低（冠军）和最高（菜鸟）的运动员编号。

代码步骤

输入处理：
- 读取运动员数量 n。
- 循环读取每个运动员的信息，包括编号和射击坐标，计算得分（距离的平方和），并将编号和得分存储在列表 player_scores 中。
排序：
- 使用 sorted() 函数对 player_scores 列表进行排序，排序的关键字是每个运动员的得分。
输出：

输出得分最低的运动员编号（即排序后列表的第一个元素的编号）和得分最高的运动员编号（即排序后列表的最后一个元素的编号）。

时间复杂度分析

输入处理：
- 读取 n 个运动员的信息，每个运动员的信息处理包括字符串分割和整数转换，时间复杂度为 O(n)。
排序：
- 使用 sorted() 函数对包含 n 个元素的列表进行排序，时间复杂度为 O(n log n)。
输出：

输出操作的时间复杂度为 O(1)。

总时间复杂度为 O(n + n log n)，即 O(n log n)。

空间复杂度分析

存储运动员信息：
- 使用列表 player_scores 存储所有运动员的编号和得分，空间复杂度为 O(n)。
其他变量：

除了输入和输出的变量外，没有使用额外的数据结构，空间复杂度为 O(1)。

总空间复杂度为 O(n)。

总结

这段代码有效地解决了射击比赛的排名问题，时间复杂度主要受排序操作影响，为 O(n log n)，空间复杂度为 O(n)。代码结构清晰，逻辑简单，适合处理中小规模的数据集。对于大规模数据集，可能需要考虑更高效的排序算法或数据结构来优化性能。

我要更强

为了优化时间复杂度和空间复杂度，我们可以考虑以下几点：

避免不必要的排序：我们只需要找到距离最小的和最大的，不需要对所有数据进行排序。
使用更有效的数据结构：例如，使用字典（dict）来存储运动员的编号和得分，可以快速查找。
减少内存分配：避免在循环中进行大量的列表追加操作，这可能会导致多次内存分配。

下面是优化后的代码：

# 读取运动员数量
n = int(input())

# 初始化字典存储运动员信息
player_scores = {}

# 读取每个运动员的信息并计算得分
for _ in range(n):
    # 读取一行输入，分割成列表
    player_info = input().split()
    # 运动员编号
    player_id = player_info[0]
    # 射击坐标
    x, y = map(int, player_info[1:])
    # 计算得分（距离的平方和）
    score = x**2 + y**2
    # 存储到字典中
    player_scores[player_id] = score

# 找到得分最小的运动员
min_score_player = min(player_scores, key=player_scores.get)
# 找到得分最大的运动员
max_score_player = max(player_scores, key=player_scores.get)

# 输出结果
print(f"{min_score_player} {max_score_player}")

时间复杂度分析

输入处理：
- 读取 n 个运动员的信息，每个运动员的信息处理包括字符串分割和整数转换，时间复杂度为 O(n)。
查找最小和最大得分：

使用 min() 和 max() 函数查找字典中的最小和最大值，时间复杂度为 O(n)。

总时间复杂度为 O(n)。

空间复杂度分析

存储运动员信息：

使用字典 player_scores 存储所有运动员的编号和得分，空间复杂度为 O(n)。

总空间复杂度为 O(n)。

总结

这段优化后的代码避免了不必要的排序操作，使用字典来存储和快速查找运动员信息，有效地减少了时间复杂度和空间复杂度。时间复杂度从 O(n log n) 降低到 O(n)，空间复杂度保持为 O(n)。这种优化特别适用于处理大规模数据集，可以显著提高程序的执行效率。

哲学和编程思想

优化这段代码所使用的方法体现了以下哲学和编程思想：

KISS原则（Keep It Simple, Stupid）：
- 代码简洁明了，避免不必要的复杂性。例如，使用字典直接存储和查找运动员信息，而不是通过排序来找到最小和最大值。
YAGNI原则（You Ain't Gonna Need It）：
- 只实现当前需要的功能，不预先实现未来可能需要的功能。在这个例子中，我们只关注找到最小和最大值的运动员，而不是对所有运动员进行排序。
效率优化：
- 通过减少不必要的数据处理和排序，提高了程序的执行效率。这体现了对时间和空间复杂度的关注，是算法和数据结构设计中的重要思想。
数据结构的选择：
- 使用字典（dict）作为数据结构，利用了字典在查找操作上的高效性（平均时间复杂度为O(1)）。这体现了在编程中选择合适数据结构的重要性。
函数式编程思想：
- 使用 map() 函数将字符串转换为整数，以及使用 min() 和 max() 函数直接找到最小和最大值，这些都体现了函数式编程中避免副作用、强调函数组合和使用高阶函数的思想。
抽象和模块化：
- 代码中的每个部分都有明确的功能，如输入处理、数据存储、结果查找和输出。这种模块化的设计使得代码更易于理解和维护。
实用主义：

代码的优化是基于实际需求和性能考虑，而不是追求理论上的最优解。这种实用主义的态度在实际编程中非常重要，它确保了代码既高效又易于理解和维护。

通过这些哲学和编程思想的应用，能够编写出既高效又易于理解的代码，这是软件开发中的一个重要目标。

举一反三

基于上述哲学和编程思想，以下是一些实用的技巧和建议，可以帮助在编程中举一反三：

保持代码简洁：
- 避免过度设计，只实现当前明确需要的功能。
- 使用简单的数据结构和算法，除非有明确的性能需求。
- 编写清晰、直观的代码，避免复杂的控制流和嵌套。
选择合适的数据结构：
- 根据操作的类型（如查找、插入、删除）选择最合适的数据结构。
- 了解不同数据结构的性能特点，如数组、链表、栈、队列、树、图、哈希表等。
- 在需要快速查找的地方使用哈希表（如Python中的字典）。
优化时间和空间复杂度：
- 分析算法的时间和空间复杂度，寻找优化的机会。
- 避免不必要的计算和数据复制。
- 使用缓存或记忆化技术来避免重复计算。
函数式编程技巧：
- 使用高阶函数（如map、filter、reduce）来处理数据集合。
- 利用函数式编程的不可变性和纯函数来减少副作用。
- 使用递归或迭代来处理问题，根据问题的特性选择最合适的方法。
模块化和抽象：
- 将代码分解为小的、可重用的模块。
- 使用抽象来隐藏实现细节，提供清晰的接口。
- 编写测试来确保模块的正确性和独立性。
实用主义：
- 根据实际需求和性能目标来选择解决方案。
- 不要为了追求理论上的最优解而牺牲代码的可读性和可维护性。
- 在实际应用中不断测试和调整，以找到最适合的解决方案。
持续学习和实践：