LeetCode算法题-Minimum Index Sum of Two Lists（Java实现）

这是悦乐书的第272次升级，第286篇原创

01 看题和准备

今天详情的是LeetCode算法题中Easy级别的第139题（顺位题号是599）。假设Andy和Doris想要选择一家餐馆吃晚餐，他们都有一个最受欢迎的餐馆列表。你需要用最少的列表索引总和帮助他们找出他们的共同兴趣。假如答案之间存在选择关系，则输出所有答案并且没有顺序要求。你可以假设总有一个答案。例如：

输入:

[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]

[“Piatti”, “The Grill at Torrey Pines”, “Hungry Hunter Steakhouse”, “Shogun”]

输出: [“Shogun”]

说明: 他们都喜欢的唯逐个家餐厅是“Shogun”。

输入:

[“Shogun”, “Tapioca Express”, “Burger King”, “KFC”]

[“KFC”, “Shogun”, “Burger King”]

输出: [“Shogun”]

说明: 他们喜欢并且索引总和最少的餐馆是“Shogun”，索引和1（0 + 1）。

注意：

• 两个列表的长度将在[1,1000]的范围内。

• 两个列表中的字符串长度将在[1,30]的范围内。

• 索引从0开始到列表长度减去1。

• 两个列表中都没有重复项。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

使用两个HashMap，分别将list1和list2的元素存入其中，以元素值为key，索引为value。定义一个最小值min，初始值为int的最大值，而后遍历其中一个map的key值，假如第二个map中也存在该key，此时分为两种情况解决。

第一种情况，假如该key值对应两索引之和小于min，那么将min升级，再将结果数组清空，再将该key增加进结果数组。

第二种情况，假如该key值对应两索引之和等于min，表明存在另外一对索引之和，直接将key增加进结果数组就可。

最后返回结果数组。

public String[] findRestaurant(String[] list1, String[] list2) {    Map<String, Integer> map = new HashMap<>();    Map<String, Integer> map2 = new HashMap<>();    for(int i=0; i<list1.length; i++){        map.put(list1[i], i);    }    for(int i=0; i<list2.length; i++){        map2.put(list2[i], i);    }    int min = Integer.MAX_VALUE;    List<String> result = new ArrayList<>();    for (String key : map.keySet()) {        if (map2.containsKey(key)) {            if (map.get(key)+map2.get(key) < min) {                min = map.get(key)+map2.get(key);                result = new ArrayList<>();                result.add(key);            } else if (map.get(key)+map2.get(key) == min) {                result.add(key);            }        }    }    return result.toArray(new String[result.size()]);}

03 第二种解法

我们可以将第一种解法再简化下，只使用一个HashMap，而后遍历剩下的那个数组，判断思路与第一种解法一致。同时，我们也可以将循环内部使用创立新对象来清空数组的方法，换成其自身的clear()方法。

public String[] findRestaurant2(String[] list1, String[] list2) {    Map<String, Integer> map = new HashMap<>();    for(int i=0; i<list1.length; i++){        map.put(list1[i], i);    }    int min = Integer.MAX_VALUE;    List<String> result = new ArrayList<>();    for (int i=0; i<list2.length; i++) {        if (map.containsKey(list2[i])) {            if (map.get(list2[i])+i < min) {                min = map.get(list2[i])+i;                result.clear();                result.add(list2[i]);            } else if (map.get(list2[i])+i == min) {                result.add(list2[i]);            }        }    }    return result.toArray(new String[result.size()]);}

04 第三种解法

我们也可以不使用HashMap，直接使用for循环来处理。

public String[] findRestaurant3(String[] list1, String[] list2) {    int min = Integer.MAX_VALUE;    List<String> result = new ArrayList<>();    for (int i=0; i<list1.length; i++) {        for (int j=0; j<list2.length; j++) {            if (list1[i].equals(list2[j])) {                if (j+i < min) {                    min = j+i;                    result.clear();                    result.add(list1[i]);                } else if (j+i == min) {                    result.add(list1[i]);                }            }        }    }    return result.toArray(new String[result.size()]);}

05 小结

算法专题目前已日更超过四个月，算法题文章139+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是一律内容，假如大家有什么好的解法思路、建议或者者其余问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！