這篇文章主要講解了“Python怎么實現(xiàn)兩個列表的最小索引總和”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Python怎么實現(xiàn)兩個列表的最小索引總和”吧！

在蕭山等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供做網(wǎng)站、網(wǎng)站制作 網(wǎng)站設(shè)計制作定制網(wǎng)站設(shè)計,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),全網(wǎng)營銷推廣,成都外貿(mào)網(wǎng)站建設(shè)公司,蕭山網(wǎng)站建設(shè)費(fèi)用合理。

題目：

假設(shè) Andy 和 Doris 想在晚餐時選擇一家餐廳，并且他們都有一個表示最喜愛餐廳的列表，每個餐廳的名字用字符串表示。

你需要幫助他們用最少的索引和找出他們共同喜愛的餐廳。如果答案不止一個，則輸出所有答案并且不考慮順序。你可以假設(shè)總是存在一個答案。

示例 1:

輸入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
輸出: ["Shogun"]
解釋: 他們唯一共同喜愛的餐廳是“Shogun”。

示例 2:

輸入:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
輸出: ["Shogun"]
解釋: 他們共同喜愛且具有最小索引和的餐廳是“Shogun”，它有最小的索引和1(0+1)。

提示:

1. 兩個列表的長度范圍都在 [1, 1000] 內(nèi)。

2. 兩個列表中的字符串的長度將在 [1，30] 的范圍內(nèi)。

3. 下標(biāo)從 0 開始，到列表的長度減 1。

4. 兩個列表都沒有重復(fù)的元素。

解題思路：

兩個字符串?dāng)?shù)組，找重復(fù)出現(xiàn)的元素，返回其索引和最小的目標(biāo)數(shù)組。最容易想到的解法就是用哈希映射解題，Key 存儲其數(shù)組的每個元素值，Value 存儲其下標(biāo)索引。第一次遍歷將其中一個數(shù)組添加到哈希映射，第二次遍歷查找目標(biāo)元素。需要維護(hù)一個最小索引和來保證查詢的目標(biāo)索引和為最小。

哈希表解題：

Java：

class Solution {
 public String[] findRestaurant(String[] list1, String[] list2) {
 Map<String, Integer> map = new HashMap<>();//建立哈希映射
 for (int i = 0; i < list1.length; i++)//初次遍歷將一個數(shù)組建立映射關(guān)系
 map.put(list1[i], i);
 List<String> res = new ArrayList<>();//待返回的目標(biāo)數(shù)組
 int sum = Integer.MAX_VALUE;//sum為當(dāng)前滿足條件的最小索引和
 for (int i = 0; i < list2.length; i++) {//第二次遍歷查找目標(biāo)元素
 if (map.containsKey(list2[i])) {
 int tmp = i + map.get(list2[i]);//當(dāng)前索引和
 if (tmp < sum) {//如果當(dāng)前索引和更小
 res.clear();//清除目標(biāo)數(shù)組
 res.add(list2[i]);//添加該元素
 sum = tmp;// 刷新最小索引和
 } else if (tmp == sum)//如果索引和相等
 res.add(list2[i]);//只添加元素
 }
 }
 return res.toArray(new String[res.size()]);//轉(zhuǎn)成 string 數(shù)組
 }
}

Python：

class Solution:
 def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
 hash_map = dict()# 建立哈希映射
 for i, s in enumerate(list1):# 初次遍歷將一個數(shù)組建立映射關(guān)系
 hash_map[s] = i
 min_sum = 2001# 當(dāng)前滿足條件的最小索引和
 res = list()# 待返回的目標(biāo)數(shù)組
 for i, s in enumerate(list2):# 第二次枚舉遍歷查找目標(biāo)元素
 if s in hash_map:
 tmp = i+hash_map[s]# 當(dāng)前索引和
 if tmp < min_sum:# 如果當(dāng)前索引和更小
 res.clear()# 清除目標(biāo)數(shù)組
 res.append(s)# 添加該元素
 min_sum = tmp# 刷新最小索引和
 elif tmp == min_sum:# 如果索引和相等
 res.append(s)# 只添加元素
 return res

操作索引解題：

這種解法非常巧妙，雖然效率很低。以下解釋摘自 LeetCode，可以作為參考擴(kuò)展思路：

另一種可以遍歷不同 sumsum (下標(biāo)和)，并判斷是否有字符串分別出現(xiàn)在 list1 和 list2 中且下標(biāo)和為 sum。

現(xiàn)在我們知道下標(biāo)和的值 sum 數(shù)值范圍從 0 到 m + n - 1。這里 m 和 n 分別是 list1 和 list2 的長度，我們現(xiàn)在可以升序枚舉 sum ，對于每個 sum，我們遍歷 list1，假設(shè)當(dāng)前下標(biāo)為 i，為了得到下標(biāo)和 sum，list2 中的下標(biāo) j 為 sum?i。通過這樣的辦法，我們不需要遍歷 list2，而可以直接通過計算得到在 list2 中對應(yīng)的下標(biāo)。

對于每個 sum，我們遍歷 list1 的所有下標(biāo)，一旦有 list1 和 list2 中的字符串匹配，就把匹配字符串放入一個 res 列表中。

我們對 sum 升序數(shù)組中所有值做相同的過程，對于每個 sum 遍歷完一遍 list1 之后，我們檢查 res 列表是否為空。如果是空的，我們繼續(xù)遍歷下一個 sum 數(shù)組。如果不為空，當(dāng)前的 res 就是最小下標(biāo)和的數(shù)組。這是因為我們遍歷 sum 的順序是升序的，所以第一個找到的列表就是結(jié)果列表。

Java：

class Solution {
 public String[] findRestaurant(String[] list1, String[] list2) {
 List<String> res = new ArrayList<>();
 for (int sum = 0; sum < list1.length + list2.length - 1; sum++) {
 for (int i = 0; i <= sum; i++) {
 if (i < list1.length && sum - i < list2.length && list1[i].equals(list2[sum - i]))
 res.add(list1[i]);
 }
 if (res.size() > 0) break;//一旦找到最小索引和序列直接結(jié)束遍歷，因為sum是遞增的，之后得到的索引和一定更大
 }
 return res.toArray(new String[res.size()]);
 }
}

Python

class Solution:
 def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
 res = list()
 list1_size, list2_size = len(list1), len(list2)
 for min_sum in range(list1_size+list2_size-1):
 for i in range(min_sum+1):
 if i < list1_size and min_sum-i < list2_size and list1[i] == list2[min_sum-i]:
 res.append(list1[i])
 if len(res) > 0:# 一旦找到最小索引和序列直接結(jié)束遍歷，因為sum是遞增的，之后得到的索引和一定更大
 break
 return res

感謝各位的閱讀，以上就是“Python怎么實現(xiàn)兩個列表的最小索引總和”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Python怎么實現(xiàn)兩個列表的最小索引總和這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！

分享標(biāo)題：Python怎么實現(xiàn)兩個列表的最小索引總和
文章鏈接：http://chinadenli.net/article40/gspgeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、靜態(tài)網(wǎng)站、網(wǎng)站導(dǎo)航、虛擬主機(jī)、營銷型網(wǎng)站建設(shè)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)