Skip to content

Latest commit

 

History

History
260 lines (216 loc) · 6.42 KB

README.md

File metadata and controls

260 lines (216 loc) · 6.42 KB
Raw
comments difficulty edit_url tags
true
简单
数组
哈希表
字符串

599. 两个列表的最小索引总和

English Version

题目描述

假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。

 

示例 1:

输入: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
输出: ["Shogun"]
解释: 他们唯一共同喜爱的餐厅是“Shogun”。

示例 2:

输入:list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 = ["KFC", "Shogun", "Burger King"]
输出: ["Shogun"]
解释: 他们共同喜爱且具有最小索引和的餐厅是“Shogun”，它有最小的索引和1(0+1)。

 

提示:

  • 1 <= list1.length, list2.length <= 1000
  • 1 <= list1[i].length, list2[i].length <= 30 
  • list1[i] 和 list2[i] 由空格 ' ' 和英文字母组成。
  • list1 的所有字符串都是 唯一 的。
  • list2 中的所有字符串都是 唯一 的。

解法

方法一

Python3

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        ans = []
        mp = {v: i for i, v in enumerate(list2)}
        mi = 2000
        for i, v in enumerate(list1):
            if v in mp:
                t = i + mp[v]
                if t < mi:
                    mi = t
                    ans = [v]
                elif t == mi:
                    ans.append(v)
        return ans

Java

class Solution {

    public String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> mp = new HashMap<>();
        for (int i = 0; i < list2.length; ++i) {
            mp.put(list2[i], i);
        }
        List<String> ans = new ArrayList<>();
        int mi = 2000;
        for (int i = 0; i < list1.length; ++i) {
            if (mp.containsKey(list1[i])) {
                int t = i + mp.get(list1[i]);
                if (t < mi) {
                    ans = new ArrayList<>();
                    ans.add(list1[i]);
                    mi = t;
                } else if (t == mi) {
                    ans.add(list1[i]);
                }
            }
        }
        return ans.toArray(new String[0]);
    }
}

C++

class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        unordered_map<string, int> mp;
        for (int i = 0; i < list2.size(); ++i) mp[list2[i]] = i;
        int mi = 2000;
        vector<string> ans;
        for (int i = 0; i < list1.size(); ++i) {
            if (mp.count(list1[i])) {
                int t = i + mp[list1[i]];
                if (t < mi) {
                    ans.clear();
                    ans.push_back(list1[i]);
                    mi = t;
                } else if (t == mi) {
                    ans.push_back(list1[i]);
                }
            }
        }
        return ans;
    }
};

Go

func findRestaurant(list1 []string, list2 []string) []string {
	mp := make(map[string]int)
	for i, v := range list2 {
		mp[v] = i
	}
	mi := 2000
	var ans []string
	for i, v := range list1 {
		if _, ok := mp[v]; ok {
			t := i + mp[v]
			if t < mi {
				ans = []string{v}
				mi = t
			} else if t == mi {
				ans = append(ans, v)
			}
		}
	}
	return ans
}

TypeScript

function findRestaurant(list1: string[], list2: string[]): string[] {
    let minI = Infinity;
    const res = [];
    const map = new Map<string, number>(list1.map((s, i) => [s, i]));
    list2.forEach((s, i) => {
        if (map.has(s)) {
            const sumI = i + map.get(s);
            if (sumI <= minI) {
                if (sumI < minI) {
                    minI = sumI;
                    res.length = 0;
                }
                res.push(s);
            }
        }
    });
    return res;
}

Rust

use std::collections::HashMap;
use std::iter::FromIterator;

impl Solution {
    pub fn find_restaurant(list1: Vec<String>, list2: Vec<String>) -> Vec<String> {
        let map: HashMap<String, usize> = HashMap::from_iter(list1.into_iter().zip(0..));
        let mut res = vec![];
        let mut min_i = usize::MAX;
        list2
            .into_iter()
            .enumerate()
            .for_each(|(i, key)| {
                if map.contains_key(&key) {
                    let sum_i = map.get(&key).unwrap() + i;
                    if sum_i <= min_i {
                        if sum_i < min_i {
                            min_i = sum_i;
                            res.clear();
                        }
                        res.push(key);
                    }
                }
            });
        res
    }
}

方法二

C++

func findRestaurant(list1[] string, list2[] string)[] string {
mp:= make(map[string]int)
	for i, v := range list2 {
		mp[v] = i
	}
	mi := 2000
	var ans []string
	for i, v := range list1 {
        if _
            , ok : = mp[v];
        ok {
        t:
            = i + mp[v] if t < mi {
                ans = [] string { v } mi = t
            }
            else if t == mi {
                ans = append(ans, v)
            }
        }
    }
    return ans
}