每日一题——Python实现PAT甲级1041 Be Unique（举一反三+思想解读+逐步优化）

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

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

Python-3.12.0文档解读

我的写法

代码点评

时间复杂度分析

空间复杂度分析

总结

我要更强

方法1：一次遍历，使用数组模拟哈希表

方法2：双哈希表优化

方法3：使用有序字典

优化分析

小结

哲学和编程思想

1. 时间和空间权衡（Time-Space Tradeoff）

2. 单一职责原则（Single Responsibility Principle）

3. 最小化遍历次数（Minimizing Passes Over Data）

4. 哈希表和数组的使用（Hash Tables and Arrays）

5. 顺序保持（Order Preservation）

6. 空间优化（Space Optimization）

7. 提前退出（Early Exit）

具体方法中的编程思想应用总结：

举一反三

1. 理解问题和数据特性

2. 选择合适的数据结构

3. 最小化遍历次数

4. 空间优化

5. 单一职责原则

6. 时空权衡

7. 算法思想

举一反三技巧：

技巧1：模式识别

技巧2：优化现有算法

技巧3：保持代码可读性和可维护性

实例应用：

分析问题：

选择数据结构：

设计算法：

优化和测试：

题目链接

我的写法

import sys  # 导入sys模块，用于退出程序# 从标准输入读取一行，并将其转换为整数列表
# 首先分割输入的字符串，使用map函数将每个分割的部分转换为整数，然后再转换为列表
N_nums = list(map(int, input().split()))# 取出列表的第一个元素，作为N值
N = N_nums[0]# 取出列表中除第一个元素外的所有元素，作为新的列表
N_nums = N_nums[1:]# 初始化一个空字典，用于记录每个数字出现的次数
is_unique = {}# 遍历N_nums列表中的每个数字
for num in N_nums:# 检查当前数字是否在字典中if is_unique.get(num, None):# 如果数字已经在字典中，次数加1is_unique[num] += 1else:# 如果数字不在字典中，将其加入字典，并初始化次数为1is_unique[num] = 1# 遍历字典中的每个键值对
for k, v in is_unique.items():# 检查当前键的值是否为1（即该数字只出现了一次）if v == 1:# 如果找到一个只出现了一次的数字，打印该数字，并退出程序print(f"{k}")sys.exit(0)# 如果没有找到只出现一次的数字，打印"None"
print("None")

这段代码的功能是查找并输出一组整数中第一个只出现一次的数字。如果没有找到这样的数字，则输出"None"。以下是对这段代码的点评以及时间复杂度和空间复杂度的分析：

代码点评

输入处理：
- N_nums = list(map(int, input().split())) 这一行实现了从标准输入读取一行并将其转换为整数列表。这种处理方式简洁有效。
- N = N_nums[0] 取出列表的第一个元素作为N值，N_nums = N_nums[1:] 这一行将列表中除第一个元素外的所有元素提取出来。
统计数字出现次数：
- 使用一个字典 is_unique 来记录每个数字出现的次数。这种方法非常直观且有效。
- if is_unique.get(num, None): 这一行可以简化为 if num in is_unique:，这样更清晰一些。
查找目标数字：
- 遍历字典 is_unique 来查找第一个只出现一次的数字，并使用 sys.exit(0) 提前退出程序。这种方法在找到目标后立即退出，避免了不必要的遍历。
输出结果：

如果没有找到只出现一次的数字，程序会输出 "None"。

时间复杂度分析

输入处理：
- list(map(int, input().split()))：这行代码的时间复杂度为 O(N)，其中 N 是输入数字的个数。
统计数字出现次数：
- for num in N_nums:：这一循环的时间复杂度为 O(N)，因为我们需要遍历所有的数字。
- is_unique.get(num, None) 和 is_unique[num] = 1 等操作在字典中的查找和插入操作平均时间复杂度为 O(1)，所以整个循环的时间复杂度为 O(N)。
查找目标数字：

for k, v in is_unique.items():：这一循环的时间复杂度为 O(U)，其中 U 是字典中不同数字的个数。由于最多有 N 个不同的数字，最坏情况下 U 为 N，因此最坏情况下这一部分的时间复杂度为 O(N)。

综合起来，整个程序的时间复杂度为 O(N)。

空间复杂度分析

输入处理：
- N_nums 列表的空间复杂度为 O(N)。
统计数字出现次数：

is_unique 字典的空间复杂度为 O(U)，其中 U 是不同数字的个数。最坏情况下 U 为 N，因此空间复杂度为 O(N)。

综合起来，整个程序的空间复杂度为 O(N)。

总结

这段代码在实现上是高效且易于理解的。时间复杂度和空间复杂度均为 O(N)，很适合处理大量数据。在优化方面，可以将 if is_unique.get(num, None): 改为 if num in is_unique:，使代码更加清晰。总体来说，这段代码在性能和可读性上都表现良好。

我要更强

要优化这个问题，主要的思路是尝试减少对输入列表的多次遍历和对数据的额外存储。下面是一些可能的改进方法：

方法1：一次遍历，使用数组模拟哈希表

在已知数据范围的情况下，可以使用数组来替代字典，这样可以减少哈希开销。但是，这需要先假设数字的取值范围是已知的且不大，比如在[0, 100000]范围内。

import sysdef find_first_unique(nums):max_value = 100001  # 假设数字在 [0, 100000] 范围内count = [0] * max_valuefirst_position = [-1] * max_valuefor i, num in enumerate(nums):if count[num] == 0:first_position[num] = icount[num] += 1first_unique_position = len(nums)for num, cnt in enumerate(count):if cnt == 1:first_unique_position = min(first_unique_position, first_position[num])if first_unique_position == len(nums):print("None")else:print(nums[first_unique_position])sys.exit(0)N_nums = list(map(int, input().split()))
N = N_nums[0]
nums = N_nums[1:]
find_first_unique(nums)

方法2：双哈希表优化

使用两个哈希表，一个记录出现次数，另一个记录每个数字的第一次出现位置，最后遍历第一个哈希表找到只出现一次且位置最靠前的数字。

import sysdef find_first_unique(nums):count = {}first_position = {}for i, num in enumerate(nums):if num in count:count[num] += 1else:count[num] = 1first_position[num] = ifirst_unique_position = len(nums)for num, cnt in count.items():if cnt == 1:first_unique_position = min(first_unique_position, first_position[num])if first_unique_position == len(nums):print("None")else:print(nums[first_unique_position])sys.exit(0)N_nums = list(map(int, input().split()))
N = N_nums[0]
nums = N_nums[1:]
find_first_unique(nums)

方法3：使用有序字典

Python的collections.OrderedDict可以记录插入顺序，同时保留哈希表的高效查找性能。

import sys
from collections import OrderedDictdef find_first_unique(nums):count = OrderedDict()for num in nums:if num in count:count[num] += 1else:count[num] = 1for num, cnt in count.items():if cnt == 1:print(num)sys.exit(0)print("None")N_nums = list(map(int, input().split()))
N = N_nums[0]
nums = N_nums[1:]
find_first_unique(nums)

优化分析

时间复杂度：所有方法的时间复杂度均为O(N)，因为我们只需要遍历输入列表一次。
空间复杂度：

方法1的空间复杂度为O(M)，其中M是数字的范围（即max_value）。
方法2和方法3的空间复杂度为O(N)，因为在最坏情况下，我们需要存储所有数字的出现次数和位置。

小结

这些方法在时间复杂度上并没有比原始方法更优，但在某些情况下可以减少空间占用，或者代码更加简洁和清晰。希望这些方法能对问题有所帮助。

哲学和编程思想

在编写和优化算法的过程中，我们不仅要考虑代码的正确性和效率，还会运用到一些计算机科学和编程的哲学思想。这些思想能够帮助我们更好地理解问题、设计解决方案和分析性能。以下是一些相关的哲学和编程思想，以及它们在上述方法中的具体应用。