假设 Andy 和 Doris 想在晚餐时选择一家餐厅,并且他们都有一个表示最喜爱餐厅的列表,每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个,则输出所有答案并且不考虑顺序。 你可以假设答案总是存在
可以映射的实际问题:查看最近喜欢的店铺信息,根据你之前经常点外卖的信息,可以得出店铺信息,然后以他们的坐标位置和你的坐标之间算出距离进行排序。当然实际情况更为复杂。
回归本题:
【第一步】将list1存入到HashMap中,key值为list1中的元素,value值为下标。
【第二步】定义数组来存放结果(list1和list2的最近共有元素),定义max表示数组中元素的value之和。
【第三步】遍历list2数组,寻找与map集合的共有元素
【如果找到】判断当前元素与max的大小
- public static String[] findRestaurant(String[] list1, String[] list2) {
- // 1. 记录 list1到Map中 key存值,value存下标
- HashMap
map = new HashMap<>(); - for (int i = 0; i < list1.length; i++) {
- map.put(list1[i],i);
- }
- // 2. 定义数组用来存放结果
- List
res = new ArrayList<>(); - int max = Integer.MAX_VALUE;
- // 3.遍历list2 获取与list1共有的数据
-
- for (int i = 0; i < list2.length; i++) {
- if (map.containsKey(list2[i])) {
- // 对比当前元素与max的大小,如果小于则将集合中元素清除,存入新元素
- if ((i + map.get(list2[i]) < max)) {
- max = i + map.get(list2[i]);
- res.clear();
- res.add(list2[i]);
- } else if (i + map.get(list2[i]) == max){
- 如果等于则存入新元素
- res.add(list2[i]);
- }
- }
- }
- return res.toArray(res.toArray(new String[0]));
- }