题目描述
请设计一个高效算法，再给定的字符串数组中，找到包含”Coder”的字符串(不区分大小写)，并将其作为一个新的数组返回。结果字符串的顺序按照”Coder”出现的次数递减排列，若两个串中”Coder”出现的次数相同，则保持他们在原数组中的位置关系。
给定一个字符串数组A和它的大小n，请返回结果数组。保证原数组大小小于等于300,其中每个串的长度小于等于200。同时保证一定存在包含coder的字符串。
测试样例：
[“i am a coder”,”Coder Coder”,”Code”],3
返回：[“Coder Coder”,”i am a coder”]
程序代码
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct info{
int Id;
int num;
};
bool ifcoder(string str){
if((str[1]=='o'||str[1]=='O')&&(str[2]=='d'||str[2]=='D')&&
(str[3]=='e'||str[3]=='E')&&(str[4]=='r'||str[4]=='R')){
return true;
}else{
return false;
}
}
void sort(vector<info> &infov){
int len=infov.size();
for(int i=0;i<len-1;i++){
for(int j=0;j<len-i-1;j++){
if(infov[j].num<infov[j+1].num){
info t;
t.Id=infov[j].Id;
t.num=infov[j].num;
infov[j].Id=infov[j+1].Id;
infov[j].num=infov[j+1].num;
infov[j+1].Id=t.Id;
infov[j+1].num=t.num;
}
}
}
}
vector<string> findCoder(vector<string> A,int n){
vector<info> infov;
for(int i=0;i<n;i++){
int len=A[i].size();
int s=0;
for(int j=0;j<len;j++){
if((A[i][j]=='c'||A[i][j]=='C')&&(j+5<=len)){
string tempstr=A[i].substr(j,5);
if(ifcoder(tempstr)){
s++;
}
}
}
if(s>0){
info infom;
infom.Id=i;
infom.num=s;
infov.push_back(infom);
}
}
sort(infov);
vector<string> r;
for(int i=0;i<infov.size();i++){
r.push_back(A[infov[i].Id]);
cout<<A[infov[i].Id]<<endl;
}
return r;
}
int main(){
vector<string> A;
int n=4;
A.push_back("i am a coder");
A.push_back("Coder Coder");
A.push_back("Code");
A.push_back("codER adf dada coder erwt coder");
findCoder(A,n);
system("pause");
}