C++ 代码优化：时间复杂度优化 - 数字出现次数统计

#include #include #include #include #include using namespace std; typedef long long ll; ll n;

// 优化前的代码 struct node{ int num; int val; }bin[11]; bool cmp(node x,node y){ return x.val<y.val; } ll f(ll x){ ll x1=x; while(x1){ bin[x1%10].val++; bin[x1%10].num=x1%10; x1/=10; } sort(bin,bin+9+1,cmp); return bin[9].num; }

int main(void){ cin>>n; for(int i=1;i<=n;i++){ ll x,ans=0; cin>>x; for(int j=1;j<=x;j++){ memset(bin,0,sizeof(bin)); ans+=f(j); } cout<<ans<<endl; } return 0; }

优化上述代码的时间复杂度可以通过使用一个数组记录每个数字出现的次数，而不是每次都重新计算。同时，可以使用一个变量记录当前最大出现次数的数字，避免每次都排序取最大。

优化后的代码如下：

#include #include #include #include #include using namespace std; typedef long long ll; ll n; int cnt[10]; // 记录每个数字出现的次数

ll f(ll x){ ll x1=x; while(x1){ cnt[x1%10]++; x1/=10; } int max_cnt = 0; // 当前最大出现次数的数字 for(int i=0;i<=9;i++){ if(cnt[i] > cnt[max_cnt]){ max_cnt = i; } } return max_cnt; }

int main(void){ cin>>n; for(int i=1;i<=n;i++){ ll x,ans=0; cin>>x; memset(cnt,0,sizeof(cnt)); for(int j=1;j<=x;j++){ ans+=f(j); } cout<<ans<<endl; } return 0; }