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

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

题目描述

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

假设 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 中的所有字符串都是 唯一 的。

解题思路

法1

双循环
遍历l1中的每个字符串在l2中的位置,最后返回位置相加最小的字符串

我们需要申请3个变量,s用于储存当前最小的字符串,min用于储存最小值的数值

循环遍历l1套循环遍历l2就可以解决

• 时间复杂度(O(n^2))
• 空间复杂度(O(1))

但是这个方法有点消耗性能

法2

哈希表\

建立一个哈希表map[string]int,,其中key为l1与l2中出现的字符串,value记录位置之和,返回出现过两次并且和为最小的字符串数组

• 时间复杂度(O(n))
• 空间复杂度(O(n))

执行结果

法2

哈希表\

func findRestaurant(list1 []string, list2 []string) []string {
    // 将list1中所有餐厅名字存到map中
    dict := make(map[string]int)
    for i, s := range list1 {
        dict[s] = i
    }
    // 遍历list2，找到重复并记录最小索引和
    minIdxSum := len(list1) + len(list2)
    var result []string
    for i, s := range list2 {
        if j, ok := dict[s]; ok {
            idxSum := i + j
            if idxSum < minIdxSum {
                minIdxSum = idxSum
                result = []string{s}
            } else if idxSum == minIdxSum {
                result = append(result, s)
            }
        }
    }
    return result
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 28 ms , 在所有 Go 提交中击败了 45.45% 的用户 内存消耗： 7.1 MB , 在所有 Go 提交中击败了 42.15% 的用户 通过测试用例： 137 / 137

哈希优化

优化点\

两个数组同时遍历

返回值在l1中取切片,避免重复申请空间

func findRestaurant(list1 []string, list2 []string) []string {
 m := make(map[string]int)
 min := len(list1) + len(list2)
 t := 0
 for i := 1; i <= len(list1) || i <= len(list2); i++ {
  if i <= len(list1) {
   if m[list1[i-1]] != 0 {
    if min > m[list1[i-1]]+i {
     min = m[list1[i-1]] + i
     list1[0] = list1[i-1]
     t = 1
    } else if min == m[list1[i-1]]+i {
     list1[t] = list1[i-1]
     t++
    }
   } else {
    m[list1[i-1]] = i
   }
  }
  if i <= len(list2) {
   if m[list2[i-1]] != 0 {
    if min > m[list2[i-1]]+i {
     min = m[list2[i-1]] + i
     list2[0] = list2[i-1]
     t = 1
    } else if min == m[list2[i-1]]+i {
     list1[t] = list2[i-1]
     t++
    }
   } else {
    m[list2[i-1]] = i
   }
  }
 }
 return list1[:t]
}

法3