MinimumIndexSumOfTwoLists [source code]

public class MinimumIndexSumOfTwoLists {
    private Map<String, Integer> dict = new HashMap<>();

    public String[] findRestaurant(String[] list1, String[] list2) {
        List<String> res = new ArrayList<>();
        int min = Integer.MAX_VALUE;
        int[] indices1 = new int[list1.length];
        Arrays.fill(indices1, -1);
        for (int i = 0; i < list1.length; i++) dict.put(list1[i], i);
        for (int i = 0; i < list2.length; i++) {
            Integer index1 = dict.get(list2[i]);
            if (index1 == null) continue;
            int sum = index1 + i;
            if (sum <= min) {
                min = sum;
                indices1[index1] = min;
            }
        }
        for (int i = 0; i < indices1.length; i++) {
            if (indices1[i] == min) {
                res.add(list1[i]);
            }
        }
        return res.toArray(new String[0]);        
    }

    public static void main(String[] args) {
        MinimumIndexSumOfTwoLists tester = new MinimumIndexSumOfTwoLists();
        String[] input1_list1 = {"Shogun","Tapioca Express","Burger King","KFC"};
        String[] input1_list2 = {"Piatti","The Grill at Torrey Pines","Hungry Hunter Steakhouse","Shogun"};
        String[] input2_list1 = {"KFC"};
        String[] input2_list2 = {"KFC"};
        String[] input3_list1 = {"Shogun","Tapioca Express","Burger King","KFC"};
        String[] input3_list2 = {"KFC","Shogun","Burger King"};
        String[] res1 = tester.findRestaurant(input3_list1, input3_list2);
        System.out.println(res1.length);
        for (String s : res1) System.out.print(s + " ");
        System.out.println();
    }
}

要计算index 的 sum 什么的问题, 想到做一个反向 table 其实还是比较常见的;

这里 indices1一开始要初始化到-1, 是因为: 0在这个题目当中是可能有意义的, 比如这里的 input2. 所以为了让 indices1的初始值具有类似 sentinal 那样的区别功能, 就初始化到-1;

速度是33ms, 63%. 算法本身其实很粗糙, 所以这个速度也可以接受了;

Problem Description

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list
of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If
there is a choice tie between answers, output all of them with no order requirement. You
could assume there always exists an answer.

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).
Note:
The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.
Difficulty:Easy
Category:Algorithms
Acceptance:49.15%
Contributors:
love_Fawn
Topics:
Hash Table
You might like:
(E) Intersection of Two Linked Lists
Company:
Yelp