599. Minimum Index Sum of Two Lists 两种解法


题目描述参见leetcode

解法1:扫描两个列表,如果发现第一个列表的字符串和第二个列表的相等,而且下标之和也小于等于之前记录的最小值,那么就把答案加入,这样子就有可能记录局部最小值的答案,所以需要记录每次再记录下当前答案的局部最小值,最后筛掉就可以了
class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> ans, ansFinal;
        vector<int> indexSum;
        if (list1.size() == 0 || list2.size() == 0){
            return ans;
        }
        
        int MIN = 0x7fffffff;
        for (int i = 0; i < list1.size(); ++i){
            string s1 = list1[i];
            for (int j = 0; j < list2.size(); ++j){
                string s2 = list2[j];
                if (s1 == s2 && i + j <= MIN){
                    MIN = i + j;
                    ans.push_back(s1);
                    indexSum.push_back(i + j);
                }
            }
        }
        
        for (int i = 0; i < indexSum.size(); ++i){
            if (indexSum[i] == MIN){
                ansFinal.push_back(ans[i]);
            }
        }
        
        return ansFinal;
    }
};


解法二:把其中一个列表的字符串用map<string, int>存起来, 相同的字符串只存下标最小的(下标和最小),然后遍历另一个列表,相同的字符串下标加上map的value就是两个下表和。复杂度由O(n^2)变为O(nlogn):
class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> ans;
        map<string, int> mp;
        
        if (list1.size() == 0 || list2.size() == 0){
            return ans;
        }
        
        for (int i = 0; i < list1.size(); ++i){
            map<string, int>::iterator it = mp.find(list1[i]);
            if (it == mp.end()){
                mp[list1[i]] = i;
            }
        }
        
        int sum = 0x7fffffff;
        for (int j = 0; j < list2.size(); ++j){
            map<string , int>::iterator it = mp.find(list2[j]);
            if (it != mp.end()){
                if (sum == mp[list2[j]] + j){
                    ans.push_back(list2[j]);
                }
                if (mp[list2[j]] + j < sum){
                    sum = mp[list2[j]] + j;
                    ans.clear();
                    ans.push_back(list2[j]);
                }
            }
        }
        
        return ans;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部