当前位置：首页 > news >正文

PTA编程题实战：如何高效过滤重复大写字母（附C语言/Python双解）

news 2026/9/5 1:08:33

PTA编程实战：高效过滤重复大写字母的算法设计与实现

在编程竞赛和日常算法练习中，字符串处理是基础但至关重要的技能。PTA（Programming Teaching Assistant）平台上的这类题目考察的不仅是基本语法掌握程度，更是对算法效率和数据结构的理解深度。本文将深入探讨如何高效解决"输出不重复大写字母"这一经典问题，提供C语言和Python两种实现方案，并分析各自的优劣与适用场景。

1. 问题分析与算法设计

题目要求我们从一个输入字符串中提取所有出现过的大写字母，按照原始顺序输出且每个字母只出现一次。如果没有大写字母则输出"Not Found"。看似简单的需求背后隐藏着几个关键挑战：

顺序保持：必须按照字母在原始字符串中首次出现的顺序输出
去重处理：每个字母只能输出一次，无论它在输入中出现多少次
效率考量：当处理长字符串时，算法的时间复杂度直接影响性能

1.1 暴力解法分析

最直观的解法是使用双重循环：

// 伪代码示例 for 每个字符 in 输入字符串: if 是大写字母: for 每个已存储字符: if 已经存在: 跳过 if 不存在: 存储该字符

这种方法虽然简单，但时间复杂度达到O(n²)，当字符串较长时性能明显下降。我们需要更优的解决方案。

1.2 优化思路

高效算法需要考虑以下方面：

数据结构选择：需要快速判断字母是否已存在
顺序保持机制：记录首次出现的位置
空间复杂度：合理利用内存资源

2. C语言高效实现

C语言作为系统级编程语言，需要开发者手动管理内存和数据结构。以下是优化后的实现方案：

2.1 基于标记数组的解法

#include <stdio.h> #include <ctype.h> #include <string.h> #define MAX_LEN 82 #define ALPHABET_SIZE 26 int main() { char str[MAX_LEN]; fgets(str, MAX_LEN, stdin); // 更安全的输入方式 int exists[ALPHABET_SIZE] = {0}; // 标记字母是否已存在 char result[ALPHABET_SIZE + 1]; // 存储结果 int pos = 0; for (int i = 0; str[i] != '\0'; i++) { if (isupper(str[i])) { int index = str[i] - 'A'; if (!exists[index]) { exists[index] = 1; result[pos++] = str[i]; } } } if (pos == 0) { printf("Not Found\n"); } else { result[pos] = '\0'; printf("%s\n", result); } return 0; }

关键优化点：

使用isupper()标准函数判断大写字母
创建长度为26的标记数组，实现O(1)时间复杂度的存在性检查
总体时间复杂度降至O(n)，空间复杂度O(1)（固定大小数组）

2.2 性能对比

方法	时间复杂度	空间复杂度	适合场景
双重循环	O(n²)	O(n)	短字符串
标记数组	O(n)	O(1)	通用方案

3. Python高级实现

Python凭借其丰富的数据结构和简洁语法，可以用更少的代码实现相同功能，同时保持高性能。

3.1 基于有序字典的解法

from collections import OrderedDict def filter_uppercase(s): # 使用有序字典自动处理顺序和去重 unique_upper = OrderedDict.fromkeys( (c for c in s if c.isupper()), None ) return ''.join(unique_upper) if unique_upper else "Not Found" # 使用示例 input_str = input().strip() print(filter_uppercase(input_str))

实现优势：

OrderedDict同时保证顺序和唯一性
生成器表达式(c for c in s if c.isupper())节省内存
代码简洁易读，仅需4行核心逻辑

3.2 替代方案对比

# 方案1：使用列表和成员检查 def method1(s): seen = [] for c in s: if c.isupper() and c not in seen: seen.append(c) return ''.join(seen) if seen else "Not Found" # 方案2：使用集合辅助检查 def method2(s): seen = set() result = [] for c in s: if c.isupper() and c not in seen: seen.add(c) result.append(c) return ''.join(result) if result else "Not Found"

性能分析：

方法	时间复杂度	特点
OrderedDict	O(n)	代码最简洁
列表+成员检查	O(n²)	最直观但性能差
集合+列表	O(n)	平衡性能和可读性

提示：在Python 3.7+中，普通dict也已保持插入顺序，可以替代OrderedDict

4. 算法扩展与变种

掌握基础解法后，我们可以探讨几个相关变种问题，提升编程能力。

4.1 变种1：忽略大小写去重

要求：不区分大小写，保留首次出现的字母形式

def case_insensitive_unique(s): seen = set() result = [] for c in s: lower = c.lower() if lower not in seen: seen.add(lower) result.append(c) return ''.join(result)

4.2 变种2：统计字母出现位置

要求：输出每个字母及其所有出现位置

from collections import defaultdict def char_positions(s): positions = defaultdict(list) for idx, c in enumerate(s): if c.isupper(): positions[c].append(idx) return positions

4.3 性能优化技巧

处理超长字符串时的建议：

使用生成器而非列表保存中间结果
提前分配足够大的结果数组（C语言）
考虑并行处理（分块处理字符串）

5. 语言特性深度对比

理解不同语言的特性能帮助我们选择最佳解决方案。

5.1 C语言优势

内存控制：精确控制内存使用
执行效率：无额外开销，适合嵌入式环境
无依赖：不依赖标准库以外的功能

5.2 Python优势

开发效率：代码简洁，快速实现
丰富数据结构：内置高效容器类型
可扩展性：轻松处理Unicode等复杂字符

5.3 选择建议

场景	推荐语言	原因
系统编程	C	性能关键，资源受限
快速开发	Python	原型开发，脚本任务
教学演示	Python	代码清晰易理解
竞赛编程	Python	编码速度快