minimum-index-sum-of-two-lists

Minimum Index Sum of Two Lists – LeetCode 599

Problem

Description

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Answer

Better

Code

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> m;
        vector<string> ans;
        for(int i = 0; i != list1.size(); ++i)
            m[list1[i]] = i;
        int Min = 0x7fffffff;
        for(int i = 0; i != list2.size() && i <= Min; ++i){
            if(m.count(list2[i])){
                if(m[list2[i]] + i < Min){
                    Min = m[list2[i]] + i;
                    ans = vector<string>({list2[i]});
                }else if(m[list2[i]] + i == Min)
                    ans.push_back(list2[i]);
            }
        }
        return ans;
    }
};

思路

简单的利用hash表。时间复杂度$O(m+n)$，空间复杂度$O(m)$。
耗时$64$ ms，排名$2.89\%$

Better

思路

还没看到更好的思路