PAT/PTA刷题实战：L1-027‘出租’题的三种解法与效率对比（C语言实现）

L1-027‘出租’题的三种解法与效率对比C语言实现当你面对PTA题库中的L1-027题时是否曾思考过如何用更高效的方式解决这个看似简单的电话号码转换问题本文将带你深入探讨三种不同的C语言实现方案从基础的冒泡排序到高级的哈希映射助你在刷题路上事半功倍。1. 问题分析与基础解法这道题的核心要求是将11位手机号码转换为两个数组一个按降序排列且不含重复数字的arr数组以及一个记录原号码每位数字在arr中位置的index数组。我们先来看最直观的解法。基础实现思路将输入字符串转换为数字数组对数字进行降序排序去除重复数字建立原数字到新数组下标的映射// 冒泡排序双指针去重实现 void bubble_sort_and_remove_duplicates(int arr[], int size) { // 冒泡排序部分 for(int i0; isize-1; i) { for(int j0; jsize-1-i; j) { if(arr[j] arr[j1]) { int temp arr[j]; arr[j] arr[j1]; arr[j1] temp; } } } // 双指针去重部分 int unique 1; for(int i1; isize; i) { if(arr[i] ! arr[i-1]) { arr[unique] arr[i]; } } }这种实现虽然直观但存在几个明显问题冒泡排序时间复杂度为O(n²)需要额外空间存储原始号码副本查找索引时需要线性搜索2. 优化解法使用标准库函数C标准库提供了高效的排序函数qsort我们可以利用它来优化排序过程。#include stdlib.h // 比较函数用于qsort int compare_desc(const void *a, const void *b) { return (*(int*)b - *(int*)a); } void qsort_solution(char *phone) { int digits[11]; for(int i0; i11; i) { digits[i] phone[i] - 0; } // 使用qsort排序 qsort(digits, 11, sizeof(int), compare_desc); // 去重并构建arr数组 int arr[10], arr_size 0; for(int i0; i11; i) { if(i0 || digits[i] ! digits[i-1]) { arr[arr_size] digits[i]; } } // 构建index数组 printf(int[] arr new int[]{); for(int i0; iarr_size; i) { printf(%d%s, arr[i], iarr_size-1?,:); } printf(};\n); printf(int[] index new int[]{); for(int i0; i11; i) { int num phone[i] - 0; for(int j0; jarr_size; j) { if(arr[j] num) { printf(%d%s, j, i10?,:); break; } } } printf(};); }性能对比指标冒泡排序法qsort法排序时间复杂度O(n²)O(nlogn)代码复杂度高中内存使用较高中等提示qsort在不同平台实现可能不同但通常采用快速排序或归并排序效率远高于冒泡排序。3. 高级解法哈希映射思想对于这种数字映射问题哈希表是最理想的数据结构。虽然C语言没有内置哈希表但我们可以利用数组模拟。void hashmap_solution(char *phone) { int digit_present[10] {0}; // 标记数字是否出现 int digit_count[10] {0}; // 记录数字出现次数 // 统计数字出现情况 for(int i0; i11; i) { int num phone[i] - 0; digit_present[num] 1; digit_count[num]; } // 构建降序arr数组 int arr[10], arr_size 0; for(int num9; num0; num--) { if(digit_present[num]) { arr[arr_size] num; } } // 构建数字到索引的映射 int num_to_index[10]; for(int i0; iarr_size; i) { num_to_index[arr[i]] i; } // 输出结果 printf(int[] arr new int[]{); for(int i0; iarr_size; i) { printf(%d%s, arr[i], iarr_size-1?,:); } printf(};\n); printf(int[] index new int[]{); for(int i0; i11; i) { int num phone[i] - 0; printf(%d%s, num_to_index[num], i10?,:); } printf(};); }三种方法对比分析特性冒泡排序法qsort法哈希映射法时间复杂度O(n²)O(nlogn)O(n)空间复杂度O(n)O(n)O(1)代码复杂度高中低适合场景教学示例一般OJ高频刷题扩展性差中好4. 实战选择与优化建议在实际刷题中选择哪种方法取决于具体场景时间紧迫时哈希映射法是最佳选择编写快速且运行高效追求代码清晰qsort法平衡了性能和可读性学习目的冒泡排序法有助于理解基础算法常见优化技巧预处理数字0-9的ASCII值避免重复计算使用位运算替代数组标记减少内存使用合并输出步骤减少I/O操作时间// 优化后的哈希映射实现 void optimized_hash_solution(char *phone) { unsigned int present 0; // 用位标记数字出现 for(int i0; i11; i) { present | 1 (phone[i]-0); } int arr[10], arr_size 0; for(int num9; num0; num--) { if(present (1num)) { arr[arr_size] num; } } int num_to_index[10]; for(int i0; iarr_size; i) { num_to_index[arr[i]] i; } // 合并输出减少printf调用 char output[256]; char *p output; p sprintf(p, int[] arr new int[]{); for(int i0; iarr_size; i) { p sprintf(p, %d%s, arr[i], iarr_size-1?,:); } p sprintf(p, };\nint[] index new int[]{); for(int i0; i11; i) { p sprintf(p, %d%s, num_to_index[phone[i]-0], i10?,:); } sprintf(p, };); printf(%s, output); }在PTA等OJ系统中这种优化可能带来10-30ms的性能提升对于大量测试用例或时间限制严格的题目尤为重要。