PTA刷题避坑指南：L1-027‘出租’题的双指针去重与下标映射详解

PTA刷题避坑指南L1-027‘出租’题的双指针去重与下标映射详解当你第一次看到PTA平台L1-027这道出租题时可能会觉得它不过是个简单的字符串处理问题。但真正动手实现时很多人会陷入去重逻辑混乱、下标查找效率低下的困境。本文将从算法优化的角度带你重新审视这道经典题目。1. 问题本质与常见误区这道题的核心要求可以分解为两个部分首先将11位手机号码中的数字按降序排列并去重其次为原始号码中的每一位数字找到其在去重后数组中的索引位置。表面上看这似乎只需要基本的排序和查找操作但实际编码时会遇到几个典型问题去重逻辑混乱很多初学者会尝试在排序过程中直接去重导致算法复杂度骤增下标查找低效使用线性查找处理11位号码虽然可行但缺乏扩展性代码冗余常见实现中存在大量重复的数组拷贝和转换操作最容易被忽视的一个事实题目中的arr数组实际上是原始号码的数字指纹而index数组则是这个指纹的映射关系。理解这一点对优化代码结构至关重要。2. 双指针去重的艺术原始解法使用了冒泡排序双指针去重的组合。虽然可行但存在优化空间。让我们先看一个更优雅的双指针实现def deduplicate_sorted(arr): if not arr: return 0 slow 0 for fast in range(1, len(arr)): if arr[fast] ! arr[slow]: slow 1 arr[slow] arr[fast] return slow 1这个版本有几个关键改进前置条件检查处理空数组边缘情况指针初始化slow指针始终指向当前唯一序列的末尾元素比较只在不相等时才移动slow指针实际应用时需要注意双指针去重必须在有序数组上操作。因此我们应先排序再去重numbers list(map(int, phone_number)) numbers_sorted sorted(numbers, reverseTrue) unique_len deduplicate_sorted(numbers_sorted) unique_numbers numbers_sorted[:unique_len]3. 下标查找的优化策略原始解法使用线性查找建立索引映射时间复杂度为O(n²)。对于固定11位号码尚可接受但不够优雅。我们可以用哈希表进行优化index_map {num: idx for idx, num in enumerate(unique_numbers)} index_array [index_map[num] for num in numbers]这种方法的优势在于时间复杂度降为O(n)预处理阶段建立哈希表是O(n)后续每次查找是O(1)代码更简洁列表推导式取代了显式循环扩展性强适用于任意长度的号码处理性能对比方法时间复杂度11位号码100位号码线性查找O(n²)121次操作10,000次操作哈希表O(n)22次操作200次操作4. 通用化解决方案题目限定11位号码但优秀的代码应该具备处理任意长度输入的能力。以下是通用化改进输入验证def validate_phone(phone_str): if not phone_str.isdigit(): raise ValueError(输入必须为纯数字) return list(map(int, phone_str))动态处理def process_phone_number(phone_str): numbers validate_phone(phone_str) unique_sorted sorted(set(numbers), reverseTrue) index_map {num: idx for idx, num in enumerate(unique_sorted)} return unique_sorted, [index_map[num] for num in numbers]输出格式化def format_output(unique_sorted, index_array): arr_str { ,.join(map(str, unique_sorted)) } index_str { ,.join(map(str, index_array)) } return fint[] arr new int[]{arr_str};\nint[] index new int[]{index_str};这种实现不仅更健壮而且通过使用Python内置的set去重进一步简化了代码。虽然牺牲了一点教学意义不再显式展示双指针但在实际工程中是更优选择。5. 边界情况与异常处理优秀的算法实现必须考虑各种边界情况全相同数字如11111111111预期输出arr [1],index [0,0,...,0]空输入虽然题目保证输入但通用解法应处理if not phone_str: raise ValueError(输入不能为空)非数字字符if any(not c.isdigit() for c in phone_str): raise ValueError(包含非数字字符)极长输入虽然PTA不测试但实际应用要考虑if len(phone_str) 1000: # 设置合理上限 raise ValueError(输入过长)6. 语言特性与性能取舍不同编程语言对这个问题有不同最优解。以C为例#include vector #include algorithm #include unordered_map auto process_phone(const std::string phone) { std::vectorint numbers; for (char c : phone) { numbers.push_back(c - 0); } std::vectorint unique_sorted numbers; std::sort(unique_sorted.begin(), unique_sorted.end(), std::greater()); unique_sorted.erase(std::unique(unique_sorted.begin(), unique_sorted.end()), unique_sorted.end()); std::unordered_mapint, size_t index_map; for (size_t i 0; i unique_sorted.size(); i) { index_map[unique_sorted[i]] i; } std::vectorint index_array; for (int num : numbers) { index_array.push_back(index_map[num]); } return std::make_pair(unique_sorted, index_array); }C版本利用了STL算法代码更简洁同时保持了高性能。关键点std::sortstd::greater实现降序排序std::unique实现去重需要先排序std::unordered_map实现O(1)复杂度的查找7. 测试用例设计全面验证代码需要设计多种测试用例test_cases [ (18013820100, [8,3,2,1,0], [3,0,4,3,1,0,2,4,3,4,4]), (11111111111, [1], [0]*11), (12345678901, [9,8,7,6,5,4,3,2,1,0], [8,7,6,5,4,3,2,1,0,9,1]), (98765432100, [9,8,7,6,5,4,3,2,1,0], [0,1,2,3,4,5,6,7,8,9,9]) ] for phone, expected_arr, expected_index in test_cases: arr, index process_phone_number(phone) assert arr expected_arr assert index expected_index特别要注意的边界测试所有数字相同已经严格降序排列的输入包含0的号码极值情况虽然题目固定11位8. 从题目到实际应用的延伸这道题虽然简单但涉及的技术点在实际开发中广泛应用数据指纹生成类似arr数组的去重排序结果常用于生成数据特征摘要索引映射index数组的思想在序列化/反序列化、数据压缩中很常见算法选择根据数据规模选择线性查找或哈希表是性能优化的基本功例如处理用户手机号时可能需要类似技术def analyze_phone_pattern(phone): digits [int(c) for c in phone] unique sorted(set(digits), reverseTrue) pattern [unique.index(d) for d in digits] return { unique_digits: unique, digit_variety: len(unique), pattern: pattern, is_monotonic: all(xy for x,y in zip(pattern, pattern[1:])) }这个扩展应用可以分析号码的数字分布特征用于风险控制等场景。