华为OD机试_2025 B卷_数组去重和排序（Python，100分）（附详细解题思路）

题目描述

给定一个乱序的数组，删除所有的重复元素，使得每个元素只出现一次，并且按照出现的次数从高到低进行排序，相同出现次数按照第一次出现顺序进行先后排序。

输入描述
一个数组

输出描述
去重排序后的数组

用例

输入	1,3,3,3,2,4,4,4,5
输出	3,4,1,2,5
备注	数组大小不超过100 数组元素值大小不超过100。

数组去重排序：按频次与顺序的艺术

核心解题思路

这道题的核心在于同时解决两个问题：去重和特殊排序。我们需要：

1. 删除重复元素：每个元素只保留一个
2. 按出现频次排序：出现次数多的元素排前面
3. 频次相同时按首次出现顺序排序：保持原始先后关系

关键技巧：

• 使用字典记录元素的出现次数和首次出现位置
• 分阶段处理：先统计信息，再排序输出
• 利用Python元组排序特性实现多条件排序

完整代码实现

def deduplicate_and_sort(input_str):# 统计元素信息和首次出现位置element_info = {}for index, num in enumerate(input_str):if num not in element_info:element_info[num] = [1, index]  # [出现次数, 首次位置]else:element_info[num][0] += 1  # 增加出现次数# 提取去重元素（保留首次出现的元素）unique_elements = []# 用于跟踪已添加的元素added_elements = set()for num in input_str:if num not in added_elements:unique_elements.append(num)added_elements.add(num)# 排序：频次降序 > 首次位置升序sorted_elements = sorted(unique_elements,key=lambda x: (-element_info[x][0],  # 频次降序element_info[x][1]  # 首次位置升序))return sorted_elements# 输入处理
input_str = input().split(',')# 处理并输出
result = deduplicate_and_sort(input_str)
print(','.join(result))

关键特性分析

1. 稳定去重：保留每个元素的首次出现
2. 排序准确性：
   • 高频元素优先排列
   • 相同频次元素按原始顺序排列
3. 效率优化：
   • 时间复杂度：O(n log n)（主要来自排序）
   • 空间复杂度：O(n)（存储元素信息和去重集合）
4. 边界处理：
   • 空输入处理：默认返回空列表
   • 单元素数组：直接返回该元素

算法原理解析

1. 信息统计阶段

使用字典 element_info 存储每个元素的出现次数和首次出现位置：

element_info = {}
for index, num in enumerate(input_str):if num not in element_info:element_info[num] = [1, index]  # 首次出现：计数=1，位置=当前索引else:element_info[num][0] += 1  # 非首次出现：计数增加

原理说明：

• 字典键：元素值（如"1"、"3"等）
• 字典值：包含两个元素的列表：
  • [0]：出现次数（频次）
  • [1]：首次出现位置（索引）
• enumerate() 提供遍历索引，确保位置信息准确

2. 去重阶段

保留每个元素的首次出现：

unique_elements = []
added_elements = set()for num in input_str:if num not in added_elements:unique_elements.append(num)added_elements.add(num)

原理说明：

• 集合跟踪：使用 added_elements 集合记录已处理的元素
• 首次出现处理：当元素不在集合中时添加到结果列表
• 顺序保留：遍历顺序保证结果列表保留原始首次出现顺序

3. 排序阶段

多条件排序实现：

sorted_elements = sorted(unique_elements,key=lambda x: (-element_info[x][0],  # 频次降序element_info[x][1]     # 首次位置升序)
)

原理说明：

• 双条件排序：
  1. 主要条件：出现频次降序（高频优先）
  2. 次要条件：首次出现位置升序（位置小优先）
• 负号技巧：-频次 实现降序排序（避免使用reverse参数）
• 元组排序特性：Python自动按元组顺序比较条件

示例解析（输入：1,3,3,3,2,4,4,4,5）

输入处理

input_str = "1,3,3,3,2,4,4,4,5"

处理后：

input_str = ["1", "3", "3", "3", "2", "4", "4", "4", "5"]

1. 信息统计阶段

元素	处理过程	结果统计
“1”	首次出现	["1"]: [1, 0]
“3”	首次出现	["3"]: [1, 1]
“3”	再次出现	["3"]: [2, 1]
“3”	再次出现	["3"]: [3, 1]
“2”	首次出现	["2"]: [1, 4]
“4”	首次出现	["4"]: [1, 5]
“4”	再次出现	["4"]: [2, 5]
“4”	再次出现	["4"]: [3, 5]
“5”	首次出现	["5"]: [1, 8]

最终统计结果：

element_info = {"1": [1, 0],"3": [3, 1],"2": [1, 4],"4": [3, 5],"5": [1, 8]
}

2. 去重阶段

遍历顺序: ["1","3","3","3","2","4","4","4","5"]

元素	是否已添加	操作	unique_elements结果	added_elements结果
“1”	否	添加	[“1”]	{“1”}
“3”	否	添加	[“1”,“3”]	{“1”,“3”}
“3”	是	跳过	[“1”,“3”]	{“1”,“3”}
“3”	是	跳过	[“1”,“3”]	{“1”,“3”}
“2”	否	添加	[“1”,“3”,“2”]	{“1”,“3”,“2”}
“4”	否	添加	[“1”,“3”,“2”,“4”]	{“1”,“3”,“2”,“4”}
“4”	是	跳过	[“1”,“3”,“2”,“4”]	{“1”,“3”,“2”,“4”}
“4”	是	跳过	[“1”,“3”,“2”,“4”]	{“1”,“3”,“2”,“4”}
“5”	否	添加	[“1”,“3”,“2”,“4”,“5”]	{“1”,“3”,“2”,“4”,“5”}

最终去重结果：

unique_elements = ["1", "3", "2", "4", "5"]

3. 排序阶段

对 unique_elements = ["1", "3", "2", "4", "5"] 进行排序

元素	频次	位置	排序键值元组
“1”	1	0	(-1, 0) → (-1,0)
“3”	3	1	(-3, 1) → (-3,1)
“2”	1	4	(-1, 4) → (-1,4)
“4”	3	5	(-3, 5) → (-3,5)
“5”	1	8	(-1, 8) → (-1,8)

排序规则：

1. 比较元组第一个元素（负频次）：

   • “3"和"4”：-3（频次3）优先于-1（频次1）
   • “1”、“2”、“5”：都是-1，需要进一步比较

2. 比较元组第二个元素（位置）：

   • “3”(位置1) vs “4”(位置5)：1<5 → "3"排在"4"前
   • “1”(位置0) vs “2”(位置4) vs “5”(位置8)：0<4<8 → “1”、“2”、"5"顺序不变

最终排序顺序：

1. “3”（频次最高，位置最小）
2. “4”（频次最高，位置较大）
3. “1”（频次低，位置最小）
4. “2”（频次低，位置中等）
5. “5”（频次低，位置最大）

输出结果：

3,4,1,2,5

算法变通应用

这种方法可广泛应用于：

1. 用户行为分析：找出高频操作序列
2. 日志分析：统计高频错误及其首次发生时间
3. 推荐系统：按物品流行度和新鲜度排序
4. 数据清洗：去除重复记录并保留原始版本

通过这道题，我们掌握了处理多条件排序问题的核心技巧：分阶段收集信息 → 明确排序优先级 → 利用语言特性实现排序逻辑。这种思路可以延伸到各种复杂排序场景中。