C++_Linear Time Complexity O(n)_AC_98.72%_42ms


  • 0

    Here is the new question:given two sorted vectors,we want:min(abs(vec2[j] - vec1[i])) for all i and j. Time complexity: Linear.

    Because vec1 and vec2 are sorted, so if vec2[j] > vec1[i], so we want to reduce the difference between them, we need to increase vec1[i], so we add 1 to i;
    else we will add 1 to j.

    class WordDistance {
    unordered_map<string, vector<int>> mp;
    public:
    WordDistance(vector<string>& words) {
        for(int i = 0; i < words.size(); ++i){
            mp[words[i]].push_back(i);
        }
    }
    
    int shortest(string word1, string word2) {
        vector<int> vec1 = mp[word1];
        vector<int> vec2 = mp[word2];
        int res = INT_MAX;
        int i = 0, j = 0;
        //Here is the new question:given two sorted vectors,we want:min(abs(vec2[j] - vec1[i])) for all i and j. Time complexity: Linear
        while(i < vec1.size() && j < vec2.size()){
            res = min(res, abs(vec2[j] - vec1[i]));
            if(vec2[j] > vec1[i]){
                i++;
            }else{j++;}
        }
        return res;
    }
    };
    

    0_1479071841382_A434F4E6-7C0E-426F-98F3-7CF05D2E11DF.png


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.