leetCode题解之字符最短路径解法2

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 = 0; i< S.size(); i++)
            m.insert( make_pair(S[i],i) );
        
        for( int i =0;i<S.size();i++)
        {
            if( S[i] == C )
            {
                ans.push_back(0);
            }    
            else
            {
                int k = S.size()-1;
                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; 
    }