$O(n) 解法$
题目描述
小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。
当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。
例如,2022 排在 409 前面,因为 2022 的数位之和是 6,小于 409 的数位之和 13。
又如,6 排在 2022 前面,因为它们的数位之和相同,而 6 小于 2022。
给定正整数 n,m,请问对 1 到 n 采用这种方法排序时,排在第 m 个的元素是多少?
算法1
结构体自定义排序
提前计算好每个数的数位之和($O(nlogn)$),
然后自定义cmp直接排序($O(nlogn)$)即可
时间复杂度 $O(nlogn)$
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct node{
int x,y;
}a[N];
bool cmp(node a,node b)
{
if(a.y!=b.y)return a.y<b.y;
return a.x<b.x;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
a[i].x=i;
int tmp=i;
while(tmp){
a[i].y+=tmp%10;
tmp/=10;
}
}
sort(a+1,a+1+n,cmp);
cout<<a[m].x;
}
测试时间:
算法2
(递推预处理数位和+快速选择算法) $O(n)$
通过递推(可能算是DP)预处理数位和就可以在$O(n)$时间复杂度完成计算。
接着就是选出第m小的数,那么就自然想到了“梦开始的地方”– 第K个数
这道题y总就教我们去在$O(n)$的时间复杂度下去求出第k小的数,稍微对模板修改一下,就可以AC了。
时间复杂度 $O(n)$
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N],s[N];//s[i]表示数字i的数位之和
bool cmp(int a,int b){//自定义比较函数
if(s[a]!=s[b]) return s[a]<s[b];
return a<b;
}
int quick_sort(int l,int r,int k){//快速选择算法 y总的模板
if(l>=r) return a[l];
int i=l-1,j=r+1,x=a[l+r>>1];
while(i<j){
do i++;while(cmp(a[i],x));
do j--;while(cmp(x,a[j]));
if(i<j) swap(a[i],a[j]);
}
int sl=j-l+1;
if(k<=sl) quick_sort(l,j,k);
else quick_sort(j+1,r,k-sl);
}
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++) {
a[i]=i;
/*递推求解数位之和
如果i不是10的倍数,那么它的数位之和就等于前一个数的数位之和+1。
反之,i的数位之和就等于i的第一位数字,通过动态规划的思想,s[i]=s[i/10];
*/
if(i%10) s[i]=s[i-1]+1;
else s[i]=s[i/10];
};
printf("%d",quick_sort(1,n,m));
return 0;
}
运行时间:
感谢大家!
我也是直接排序了,原来还可以这样优化