【算法刷题】按距离升序排序问题自定义排序 / 双关键字比较 题目描述与考点题目名称按距离升序排序核心问题给定一个长度为NNN的整数数组a1,a2,…,aNa_1, a_2, \dots, a_Na1,a2,…,aN和一个目标整数xxx。要求根据以下规则将数组排序第一关键字按照di∣ai−x∣d_i |a_i - x|di∣ai−x∣的绝对差值升序排序距离xxx越近的排在越前面。第二优先级如果did_idi相同则按aia_iai本身的大小升序排序数值较小的排在前面。核心考点自定义排序比较器Custom Comparator、双关键字比较逻辑、Lambda 表达式 / 结构体。 核心思路解析对于这类“多优先级排序”问题核心在于正确书写自定义比较逻辑。假设我们在比较数组中的任意两个元素AAA与BBB先计算绝对差值dA∣A−x∣d_A |A - x|dA∣A−x∣dB∣B−x∣d_B |B - x|dB∣B−x∣比较第一关键字若dA≠dBd_A \neq d_BdAdB绝对差值小的排前面返回dAdBd_A d_BdAdB。比较第二关键字若dAdBd_A d_BdAdB数值本身小的排前面返回ABA BAB。 C 完整 AC 代码#includeiostream#includevector#includecmath#includealgorithmusingnamespacestd;intmain(){// 开启快速 I/Oios::sync_with_stdio(false);cin.tie(nullptr);intn;longlongx;if(!(cinnx))return0;vectorlonglonga(n);for(inti0;in;i){cina[i];}// 自定义排序使用 Lambda 表达式捕获全局变量 xsort(a.begin(),a.end(),[x](longlongA,longlongB){longlongdAabs(A-x);longlongdBabs(B-x);// 第一关键字绝对差值升序if(dA!dB){returndAdB;}// 第二关键字差值相同时按数值本身升序returnAB;});// 输出排序后的新数组for(inti0;in;i){couta[i](in-1?: );}cout\n;return0;}❌ 易错点总结漏掉第二关键字处理只写了abs(A - x) abs(B - x)忽略了当距离相等时需要按原数值大小再次升序排序的逻辑。比较运算符写错在严格弱序比较中必须使用小于号切勿带有否则可能在相同元素较多时导致std::sort触发段错误Segmentation Fault。数据溢出陷阱当aia_iai和xxx的范围较大时ai−xa_i - xai−x可能超出int的存储限制建议统一采用long long数据类型。⏱️ 复杂度分析时间复杂度O(NlogN)\mathcal{O}(N \log N)O(NlogN)主要耗时在于对NNN个元素进行std::sort快速排序单次比较耗时为O(1)\mathcal{O}(1)O(1)。空间复杂度O(N)\mathcal{O}(N)O(N)用于存储大小为NNN的输入数组。
