首页 > 其他分享 >leetcode-599-easy

leetcode-599-easy

时间:2022-10-26 19:01:24浏览次数:47  
标签:index 599 Shogun sum list1 list2 common easy leetcode

Minimum Index Sum of Two Lists

Given two arrays of strings list1 and list2, find the common strings with the least index sum.

A common string is a string that appeared in both list1 and list2.

A common string with the least index sum is a common string such that if it appeared at list1[i] and list2[j] then i + j should be the minimum value among all the other common strings.

Return all the common strings with the least index sum. Return the answer in any order.

Example 1:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"]
Output: ["Shogun"]
Explanation: The only common string is "Shogun".
Example 2:

Input: list1 = ["Shogun","Tapioca Express","Burger King","KFC"], list2 = ["KFC","Shogun","Burger King"]
Output: ["Shogun"]
Explanation: The common string with the least index sum is "Shogun" with index sum = (0 + 1) = 1.
Example 3:

Input: list1 = ["happy","sad","good"], list2 = ["sad","happy","good"]
Output: ["sad","happy"]
Explanation: There are three common strings:
"happy" with index sum = (0 + 1) = 1.
"sad" with index sum = (1 + 0) = 1.
"good" with index sum = (2 + 2) = 4.
The strings with the least index sum are "sad" and "happy".
Constraints:

1 <= list1.length, list2.length <= 1000
1 <= list1[i].length, list2[i].length <= 30
list1[i] and list2[i] consist of spaces ' ' and English letters.
All the strings of list1 are unique.
All the strings of list2 are unique.

思路一:用两个 map 存储对应的下标,最后遍历最小的下标。优化,看了一下题解,发现不用两个 map,在遍历第二个数组的时候,此时已经能计算最小值了,直接存储当时的最小值结果就行

public String[] findRestaurant(String[] list1, String[] list2) {
    Map<String, Integer> map1 = new HashMap<>();
    Map<String, Integer> map2 = new HashMap<>();

    for (int i = 0; i < list1.length; i++) {
        map1.put(list1[i], i);
    }

    int min = Integer.MAX_VALUE;
    for (int i = 0; i < list2.length; i++) {
        if (map1.containsKey(list2[i])) {
            int val = map1.get(list2[i]) + i;
            min = Math.min(val, min);
            map2.put(list2[i], val);
        }
    }

    List<String> result = new ArrayList<>();
    for (Map.Entry<String, Integer> e : map2.entrySet()) {
        if (e.getValue() == min) {
            result.add(e.getKey());
        }
    }

    return result.toArray(new String[]{});
}

标签:index,599,Shogun,sum,list1,list2,common,easy,leetcode
From: https://www.cnblogs.com/iyiluo/p/16829652.html

相关文章