pta7-1 存在的和消失的

### PTA习题7-1分析 PTA（Programming Teaching Assistant）是一个用于编程教学和练习的在线平台，其中包含了大量针对不同难度级别的算法设计题目。对于习题 **7-1 存在的和消失的**[^1] ，其核心考察的是数组操作以及数据结构中的查找技术。 #### 题目概述 该题目通常会提供两个整数序列 A 和 B，分别表示存在的元素集合与可能消失的元素集合。目标是从这两个集合出发找出仅存在于其中一个集合而不在另一个集合中的元素。这类问题可以通过多种方法解决，包括但不限于哈希表、位运算或者排序后的双指针法。 #### 方法一：基于哈希表的方法 利用 Python 的字典或其他语言中的哈希映射可以高效实现这一功能。以下是具体代码示例： ```python def find_disappeared_and_existed(nums_a, nums_b): set_a = set(nums_a) set_b = set(nums_b) disappeared = list(set_a - set_b) # 找到只存在于 A 中的元素 existed = list(set_b - set_a) # 找到只存在于 B 中的元素 return disappeared, existed # 测试用例 nums_a = [1, 2, 3, 4, 5] nums_b = [3, 4, 5, 6, 7] disappeared, existed = find_disappeared_and_existed(nums_a, nums_b) print(f"Disappeared elements: {disappeared}") print(f"Existed elements: {existed}") ``` 上述代码通过 `set` 数据结构快速计算差集来找到差异部分 。这种方法的时间复杂度主要由构建集合的操作决定，通常是 O(n)，因此效率较高。 #### 方法二：基于排序的双指针法 如果输入的数据量较大且不允许额外空间开销，则可以选择先对两组数据进行排序再采用双指针扫描的方式完成比较。此方式虽然牺牲了一定的空间性能但减少了内存占用，在某些特定场景下更为适用。 ```python def find_diff_sorted(a_list, b_list): a_list.sort() b_list.sort() i, j = 0, 0 result_a_not_in_b = [] result_b_not_in_a = [] while i < len(a_list) and j < len(b_list): if a_list[i] < b_list[j]: result_a_not_in_b.append(a_list[i]) i += 1 elif a_list[i] > b_list[j]: result_b_not_in_a.append(b_list[j]) j += 1 else: i += 1 j += 1 # 添加剩余未匹配项 result_a_not_in_b.extend(a_list[i:]) result_b_not_in_a.extend(b_list[j:]) return result_a_not_in_b, result_b_not_in_a # 使用样例同上 diff_result = find_diff_sorted(nums_a.copy(), nums_b.copy()) print(diff_result) ``` 这里展示了如何通过对原始列表排序并应用双指针技巧逐步对比得出最终结果 。 #### 总结 无论是选用哪种策略解决问题都需要考虑实际应用场景下的约束条件比如时间限制或是存储资源可用情况等因素影响选择最合适的方案实施求解过程。