首页 > itarticle > algorithm notes: leetcode#599 minimum index sum of two lists

algorithm notes: leetcode#599 minimum index sum of two lists

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

class :
    def findRestaurant(self, list1, list2):
        """
        :type list1: List[str]
        :type list2: List[str]
        :rtype: List[str]
        """
        map1 = {res:ix for ix, res in enumerate(list1)}
        common = dict()
        minSum = len(list1) + len(list2)
        for ix, res in enumerate(list2):
            if res in map1:
                common[res] = ix+map1[res]
                minSum = min(minSum, common[res])
        return [res for res, s in common.items() if s==minSum]

Java implementation

class  {
    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> map1 = new HashMap();
        for(int i = 0; i < list1.length; i++){
            map1.put(list1[i], i);
        }
        Map<String, Integer> common = new HashMap();
        int minSum = list1.length + list2.length;
        for(int i = 0; i < list2.length; i++){
            String res = list2[i];
            if(map1.containsKey(res)){
                int curSum = i+map1.get(res);
                common.put(res, curSum);
                minSum = minSum > curSum ? curSum : minSum;
            }
        }
        List<String> ans = new ArrayList<>();
        for(Map.Entry<String, Integer> entry : common.entrySet()){
            String res = entry.getKey();
            int s = entry.getValue();
            if(s==minSum){
                ans.add(res);
            }
        }
        return ans.toArray(new String[ans.size()]);
    }
}

Time complexity

O(l₁+l₂)

Space complexity

O(l₁+l₂)

Link

599. Minimum Index Sum of Two Lists
(中文版) 算法笔记: 力扣#599 两个列表的最小索引总和