leetcode 599. Minimum Index Sum of Two Lists

落日映苍穹つ 2023-07-13 08:19 2阅读 0赞

**目录**

一、问题描述

二、代码实现

1、暴力法

2、使用HashMap

--------------------

[https://leetcode.com/problems/minimum-index-sum-of-two-lists/][https_leetcode.com_problems_minimum-index-sum-of-two-lists]

从两个人喜欢的餐厅列表中找到共同喜欢并下标之和最小的餐厅（如果有多个则将它们都返回）

## 一、问题描述 ##

测试用例：

Example 1:
    Input:
    ["Shogun", "Tapioca Express", "Burger King", "KFC"]
    ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
    Output: ["Shogun"]
    Explanation: The only restaurant they both like is "Shogun".
    
    Example 2:
    Input:
    ["Shogun", "Tapioca Express", "Burger King", "KFC"]
    ["KFC", "Shogun", "Burger King"]
    Output: ["Shogun"]
    Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

如果两者只有一个共同喜欢的餐馆，直接将其返回；如果不止一个，则返回下标之和最小的一个。两个列表均没有重复元素，长度均在\[1, 1000\]范围内，其中的元素长度均在\[1, 30\]范围内。

## 二、代码实现 ##

### 1、暴力法 ###

class Solution {
    
        //O(mn)
        public String[] findRestaurant1(String[] list1, String[] list2) {
            int sum = Integer.MAX_VALUE;
            StringBuilder sb = new StringBuilder();
            for (int i=0; i<list1.length; i++) {
                for (int j=0; j<list2.length; j++) {
                    if (list1[i].equals(list2[j])) {
                        int curSum = i + j;
                        if (curSum <= sum) {
                            sum = curSum;
                            sb.append(list1[i]+",");
                        }
                    }
                }
            }
            
            return sb.toString().split(",");
        }
    }

### 2、使用HashMap ###

class Solution {
        
        //O(m+n)
        public String[] findRestaurant2(String[] list1, String[] list2) {
            
            HashMap<String, Integer> map = new HashMap<>();
            for(int i = 0; i < list1.length; i++) {
                map.put(list1[i], i);
            }
            
            LinkedList<String> res = new LinkedList<>();
            int indexSum = Integer.MAX_VALUE;
            for(int i = 0; i < list2.length; i++) {
                // the same restaurant is existing && sum of the indexs are not greater than previous sum.
                //存在共同喜欢的餐厅，同时下标之和小于等于之前最小和
                if(map.containsKey(list2[i]) && indexSum >= map.get(list2[i]) + i) {  
                    //当前下标和小于之前最小和
                    if(indexSum > map.get(list2[i]) + i) {  
                        res =  new LinkedList<>();
                        indexSum = map.get(list2[i]) + i;
                    }
                    res.add(list2[i]);
                }
            }
            //return res.toArray(new String[res.size()]);
            return res.toArray(new String[0]);
        }
    
    }

参考：

[https://leetcode.com/problems/minimum-index-sum-of-two-lists/discuss/103714/One-HashMap][https_leetcode.com_problems_minimum-index-sum-of-two-lists_discuss_103714_One-HashMap]

[https_leetcode.com_problems_minimum-index-sum-of-two-lists]: https://leetcode.com/problems/minimum-index-sum-of-two-lists/
[https_leetcode.com_problems_minimum-index-sum-of-two-lists_discuss_103714_One-HashMap]: https://leetcode.com/problems/minimum-index-sum-of-two-lists/discuss/103714/One-HashMap