首页 > itarticle > 算法笔记: 力扣#599 两个列表的最小索引总和

算法笔记: 力扣#599 两个列表的最小索引总和

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

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 实现

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()]);
    }
}

时间复杂度

O(l₁+l₂)

空间复杂度

O(l₁+l₂)

链接

599. Minimum Index Sum of Two Lists
599. 两个列表的最小索引总和
 (English version) Algorithm Notes: Leetcode#599 Minimum Index Sum of Two Lists