每个对应位置的字符和重排前都不相同说明其中某一个字符不能超过总字符数量的一半,否则一定会有至少一个字符相同。
string x; cin>>x; char a; int n=x.size(); map<char,int>m; for(int i=0;i<n;i++){ m[x[i]]++; if (m[x[i]]>n/2){ cout<<-1; return 0; } }
要求输出任意合法的字符串
对于一般的方式如通过map找出字符还有剩余且同时与该位置原来字符不相同就输出
for (int i=0;i<n;i++){ a=x[i]; while(a==x[i]||m[a]==0){ a++; if(a>'z')a='a'; } m[a]--; cout<<a; }
这种是会超时的!!
最坏的情况就是只有两种字符且相隔25如‘a’与‘z’。每一此输出最坏寻找25次。
这里采用优先队列来维护从而提高速度。
struct node { int x; char y; bool operator < (const node & a) const { return x<a.x; } }k,kk;
priority_queue <node> q; for (auto aa:m){ k.x=aa.second,k.y=aa.first; q.push(k); } for (int i=0;i<n;i++){ k=q.top(); if (k.y==x[i]){ q.pop(); kk=q.top(); q.pop(); cout<<kk.y; kk.x--; q.push(kk); q.push(k); } else { q.pop(); cout<<k.y; k.x--; q.push(k); } }这样的话每一次输出最多寻找2次,若最多的字符与该位置上的字符相同,就使用第二个,否则直接使用最多的字符。
完整代码:
#include<bits/stdc++.h> using namespace std; struct node { int x; char y; bool operator < (const node & a) const { return x<a.x; } }k,kk; int main(){ string x; cin>>x; char a; int n=x.size(); map<char,int>m; for(int i=0;i<n;i++){ m[x[i]]++; if (m[x[i]]>n/2){ cout<<-1; return 0; } } priority_queue <node> q; for (auto aa:m){ k.x=aa.second,k.y=aa.first; q.push(k); } for (int i=0;i<n;i++){ k=q.top(); if (k.y==x[i]){ q.pop(); kk=q.top(); q.pop(); cout<<kk.y; kk.x--; q.push(kk); q.push(k); } else { q.pop(); cout<<k.y; k.x--; q.push(k); } } return 0; }