1、题目描述
2、分析
之前使用的大循环再向两边寻找的算法是 O(n^2)复杂度的,可以利用 multimap降低其复杂度。
3、代码
vector<int> shortestToChar(string S, char C) {
// 使用标准库中的multimap 存储每个字符和其下标
// multimap的优势在于key值可以重复
vector<int> ans;
multimap<char,int> m;
for( int i = ; i< S.size(); i++)
m.insert( make_pair(S[i],i) ); for( int i =;i<S.size();i++)
{
if( S[i] == C )
{
ans.push_back();
}
else
{
int k = S.size()-;
for( auto pos = m.lower_bound( C ); pos != m.upper_bound( C ); pos++ )
{ if( abs( pos->second - i ) < k )
k = abs( pos->second -i );
}
ans.push_back(k);
}
}
return ans;
}