MinimumIndexSumOfTwoListsOPT [source code]

public class MinimumIndexSumOfTwoListsOPT {
    public String[] findRestaurant(String[] list1, String[] list2) {
        HashMap < String, Integer > map = new HashMap < String, Integer > ();
        for (int i = 0; i < list1.length; i++)
            map.put(list1[i], i);
        List < String > res = new ArrayList < > ();
        int min_sum = Integer.MAX_VALUE, sum;
        for (int j = 0; j < list2.length && j <= min_sum; j++) {
            if (map.containsKey(list2[j])) {
                sum = j + map.get(list2[j]);
                if (sum < min_sum) {
                    res.clear();
                    res.add(list2[j]);
                    min_sum = sum;
                } else if (sum == min_sum)
                    res.add(list2[j]);
            }
        }
        return res.toArray(new String[res.size()]);
    }

    public static void main(String[] args) {
        MinimumIndexSumOfTwoListsOPT tester = new MinimumIndexSumOfTwoListsOPT();
        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();
    }
}

这个是 editorial 最优解, linear 的时间, 我试了一下速度是26ms, 比我的快;

这个算法跟我的非常像(我一不小心做出来的居然也是最优解, 因为是 linear的);不过我的算法细节上的优化没有他的好;
他的算法比我的算法优越的地方体现在两点:

1. j loop 的循环范围被他缩小了, j <= min_sum, 这个是一个在某些 case 里面可以大幅提速的优化; 事实上这个有点像425里面学的那个branch and bound的思路(可见很多425里面学的技术都可以应用在一般的 optimization 题目里面);
2. 他对于 tie 的情况比我处理的细腻; 我太过于纠结于premature optimization, 所以总是希望有没有 tie 的情况干脆都能够一起处理才好.但是这样带来的问题就是速度没有人家的好. 多用几个if else并不是什么丢人的事情;

另外学习一下这里用到的几个API.

submission 里面的最优解很古老. discussion 最优解跟这个算法其实大差不差;

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