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

【Python 千题 —— 算法篇】重复字符查找

news 来源：原创 2024/9/20 8:07:52

请添加图片描述

Python 千题持续更新中 ……

脑图地址 👉：⭐https://twilight-fanyi.gitee.io/mind-map/Python千题.html⭐

字符串处理

题目背景

在处理字符串时，我们经常需要分析字符的频率，找出那些出现次数超过一次的重复字符。这在数据处理、文本分析、密码学等多个领域都有广泛的应用。比如，在字符串中找出重复的字符，可以帮助我们发现数据的规律性或错误信息，甚至可以用于密码破解或压缩算法的设计。

本题目要求找出给定字符串中所有重复出现的字符，并统计每个重复字符的出现次数。这是一个经典的字符串处理问题，掌握后可以更好地理解字符频率统计和哈希表的使用。

题目描述

编写一个函数 find_duplicate_chars()，该函数接收一个字符串 s 作为输入，返回字符串中所有重复出现的字符及其出现的次数。

函数需满足以下要求：

定义函数 find_duplicate_chars(s)，返回一个字典，键为重复字符，值为出现次数。
输入为空字符串时，返回空字典。
需要忽略大小写，即 ‘A’ 和 ‘a’ 视为同一个字符。
只统计字母字符，其他字符不参与统计。

输入描述

一个字符串 s，包含大小写字母、数字、符号等。

输出描述

返回一个字典，键为重复出现的字母字符，值为其出现次数。

示例

示例 ①

输入：

# 调用 find_duplicate_chars() 函数
print(find_duplicate_chars("Programming is fun!"))

输出：

{'r': 2, 'g': 2, 'm': 2, 'i': 2, 'n': 2}

示例 ②

输入：

print(find_duplicate_chars("123456!"))

输出：

{}

代码讲解与多种解法

解法一：使用字典记录字符频率

我们可以使用 Python 的字典来记录每个字母字符出现的次数。遍历字符串时，将字符转换为小写并跳过非字母字符。然后，在统计完频率后，过滤出那些出现次数大于1的字符，形成最终的结果。

def find_duplicate_chars(s):if not s:return {}s = s.lower()  # 忽略大小写char_count = {}# 统计每个字符的频率for char in s:if char.isalpha():  # 只统计字母字符if char in char_count:char_count[char] += 1else:char_count[char] = 1# 过滤出出现次数大于1的字符return {char: count for char, count in char_count.items() if count > 1}

优点：

代码简洁，字典操作的时间复杂度为 O(n)，n 为字符串的长度。
字符频率统计直观，符合大多数应用场景。

缺点：

只能处理字母字符，不适用于复杂的字符统计需求（如需要统计数字、符号等）。

解法二：使用 `collections.Counter`

Python 标准库 collections 提供了 Counter 类，可以简化字符频率的统计过程。Counter 是一个字典的子类，专门用于计数操作。通过 Counter 可以方便地统计字符频率，并直接筛选出重复字符。

from collections import Counterdef find_duplicate_chars(s):if not s:return {}s = s.lower()char_count = Counter([char for char in s if char.isalpha()])# 过滤出重复字符return {char: count for char, count in char_count.items() if count > 1}

优点：

Counter 提供了更高效的计数方法，减少了代码量。
易于理解和使用，适合快速实现字符频率统计。

缺点：

和第一种方法一样，默认只统计字母字符。

解法三：使用集合（Set）辅助查找

我们可以通过使用两个集合来实现字符的重复查找。第一个集合用于记录遍历过的字符，第二个集合用于保存重复的字符。遍历过程中，如果当前字符已经存在于第一个集合中，则将其添加到第二个集合中。

def find_duplicate_chars(s):if not s:return {}s = s.lower()seen = set()duplicates = set()char_count = {}for char in s:if char.isalpha():if char in seen:duplicates.add(char)else:seen.add(char)# 统计重复字符的次数for char in duplicates:char_count[char] = s.count(char)return char_count