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”。

["KFC", "Shogun", "Burger King"]

說明: 他們喜歡并且索引總和最少的餐館是“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+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！