【题目来源】学而思编程数位排序【题目描述】小猴对一个数的数位之和很感兴趣今天他要按照数位之和给序列a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an排序。当两个数各个数位之和不同时将数位和较小的排在前面当数位之和相等时将数值小的排在前面保证所有整数互不相同。例如1001 10011001排在99 9999前面因为1001 10011001的数位之和是2 22而99 9999的数位之和18 1818。又如2 22排在101 101101前面因为它们的数位之和相同而2 22小于101 101101。请你帮助小猴完成这个任务。【输入】第一行包含一个正整数n nn第二行包含n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an。【输出】一行空格隔开的n nn个整数表示排序之后的序列。【输入样例】5 2 4 1 5 3【输出样例】1 2 3 4 5【核心思想】问题分析给定n nn个互不相同的正整数要求按数位和升序排序数位和相同时按数值大小升序排序。这是一个自定义排序问题关键在于设计比较函数先比较数位和再比较原数值。算法选择数位和计算通过取模和除法逐位求和自定义比较函数cmp(x, y)先比较cal(x)与cal(y)相等时比较x与y标准排序使用sort配合自定义比较函数关键步骤初始化读取n nn和数组a [ 1.. n ] a[1..n]a[1..n]数位和函数cal(x)sum 0当x 0时循环sum x % 10累加末位数字x / 10去掉末位返回sum自定义比较函数cmp(x, y)若cal(x) ! cal(y)返回cal(x) cal(y)数位和小的排前面否则返回x y数位和相等时数值小的排前面排序并输出sort(a 1, a n 1, cmp)按自定义规则排序输出排序后的数组时间/空间复杂度时间复杂度O ( n log n × d ) O(n \log n \times d)O(nlogn×d)d dd为数字位数数位和计算排序O ( n log n ) O(n \log n)O(nlogn)每次比较O ( d ) O(d)O(d)空间复杂度O ( n ) O(n)O(n)存储数组自定义排序的核心思想多级排序键第一关键字为数位和第二关键字为原数值比较函数按优先级依次判断稳定排序替代若使用稳定排序可先按数值排序再按数位和排序但自定义比较函数更直接高效数位和计算利用十进制特性通过%10和/10逐位分离适用于任意正整数互异性保证题目保证所有整数互不相同避免了相等元素时的排序歧义适用于多关键字排序类问题自定义比较函数是 C 中实现复杂排序规则的标准方法【解题思路】【算法标签】#其他排序【代码详解】#includebits/stdc.husingnamespacestd;intn,a[100005];intcal(intx)// 计算数位和{intsum0;while(x0){sumx%10;x/10;}returnsum;}boolcmp(intx,inty){if(cal(x)!cal(y)){// 数位和不同时returncal(x)cal(y);// 小的排前面}returnxy;// 否则数值小的排前面}intmain(){cinn;for(inti1;in;i)cina[i];// 输入n个数sort(a1,an1,cmp);// 按照自定义方式排序for(inti1;in;i)couta[i] ;return0;}【运行结果】5 2 4 1 5 3 1 2 3 4 5
题解：学而思编程 数位排序
【题目来源】学而思编程数位排序【题目描述】小猴对一个数的数位之和很感兴趣今天他要按照数位之和给序列a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an排序。当两个数各个数位之和不同时将数位和较小的排在前面当数位之和相等时将数值小的排在前面保证所有整数互不相同。例如1001 10011001排在99 9999前面因为1001 10011001的数位之和是2 22而99 9999的数位之和18 1818。又如2 22排在101 101101前面因为它们的数位之和相同而2 22小于101 101101。请你帮助小猴完成这个任务。【输入】第一行包含一个正整数n nn第二行包含n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an。【输出】一行空格隔开的n nn个整数表示排序之后的序列。【输入样例】5 2 4 1 5 3【输出样例】1 2 3 4 5【核心思想】问题分析给定n nn个互不相同的正整数要求按数位和升序排序数位和相同时按数值大小升序排序。这是一个自定义排序问题关键在于设计比较函数先比较数位和再比较原数值。算法选择数位和计算通过取模和除法逐位求和自定义比较函数cmp(x, y)先比较cal(x)与cal(y)相等时比较x与y标准排序使用sort配合自定义比较函数关键步骤初始化读取n nn和数组a [ 1.. n ] a[1..n]a[1..n]数位和函数cal(x)sum 0当x 0时循环sum x % 10累加末位数字x / 10去掉末位返回sum自定义比较函数cmp(x, y)若cal(x) ! cal(y)返回cal(x) cal(y)数位和小的排前面否则返回x y数位和相等时数值小的排前面排序并输出sort(a 1, a n 1, cmp)按自定义规则排序输出排序后的数组时间/空间复杂度时间复杂度O ( n log n × d ) O(n \log n \times d)O(nlogn×d)d dd为数字位数数位和计算排序O ( n log n ) O(n \log n)O(nlogn)每次比较O ( d ) O(d)O(d)空间复杂度O ( n ) O(n)O(n)存储数组自定义排序的核心思想多级排序键第一关键字为数位和第二关键字为原数值比较函数按优先级依次判断稳定排序替代若使用稳定排序可先按数值排序再按数位和排序但自定义比较函数更直接高效数位和计算利用十进制特性通过%10和/10逐位分离适用于任意正整数互异性保证题目保证所有整数互不相同避免了相等元素时的排序歧义适用于多关键字排序类问题自定义比较函数是 C 中实现复杂排序规则的标准方法【解题思路】【算法标签】#其他排序【代码详解】#includebits/stdc.husingnamespacestd;intn,a[100005];intcal(intx)// 计算数位和{intsum0;while(x0){sumx%10;x/10;}returnsum;}boolcmp(intx,inty){if(cal(x)!cal(y)){// 数位和不同时returncal(x)cal(y);// 小的排前面}returnxy;// 否则数值小的排前面}intmain(){cinn;for(inti1;in;i)cina[i];// 输入n个数sort(a1,an1,cmp);// 按照自定义方式排序for(inti1;in;i)couta[i] ;return0;}【运行结果】5 2 4 1 5 3 1 2 3 4 5
