從兩道亦可賽艇的演算法題看字典的神奇作用

01-29

字典是python中一種可變容器模型，可以存儲任意類型對象。

字典的每個鍵值(key=>value)對用冒號(:)分割，每個對之間用逗號(,)分割，整個字典包括在花括弧({})中。

在一些情況下，藉助字典可以顯著提高代碼的運行效率，在之前的一篇《從遞歸出發思考Google面試題另一種解法+24點遊戲》中，字典就起到了非常重要的作用，接下來，我們通過兩道亦可賽艇的演算法題目來說明：

Problem 1

題目來自Leetcode

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

通過Example可以很容易看出題目的意圖，最簡單粗暴的方法可以是這樣：

用IPYTHON NOTEBOOK測試結果如下：（python3.6）

但是仔細分析的話，這段代碼的運行效率並不高，對於n個數，需要兩個訓話，運算n(n-1)/2次，有沒有更快更巧妙的辦法呢？答案是肯定的，事實上，通過字典可以只需要一個循環m執行n次就可以完成。

思路如下：建立一個空字典，對於列表中的任意一個數num，如果它不在字典中，就將值i存入字典的鍵target-num ，如果它已經在字典中，說明找到了符合條件的組合，這樣只需要對列表循環一次。

代碼及測試結果如下：

Problem 2

這是一道作業題，具體出處不知道了

對於這道題目，最簡單的方法是通過兩個循環+if判斷，但不動腦的方法必然不是最高效的，如果通過字典，我們可以只用一個循環就解決問題，當然不排除通過其他數據結構可能會有更簡便的方法。

思路與上一道題目類似，就不細講了，直接上代碼和測試結果。

def crowded_cows(cowlist,k):n cowdict={}n cowdictnum = {}n maxid = -1n for i in range(len(cowlist)):n if cowdict.get(cowlist[i]) is None:n cowdict[cowlist[i]] = i n else:n if i - cowdict[cowlist[i]] <= k:n maxid = max(maxid,cowlist[i])n else:n cowdict[cowlist[i]] = i n return(maxid) n

測試結果

綜上，引入字典其實是一種典型的用空間換速度的策略，希望這兩道題目對讀者有所啟發，當然，如果文中有不當之處，或者有更好的方法，也歡迎指出。

作者：侯正平 Python愛好者社區專欄作者，請勿轉載，謝謝。
出處：從兩道亦可賽艇的演算法題看字典的神奇作用
配套視頻教程：Python3爬蟲三大案例實戰分享：貓眼電影、今日頭條街拍美圖、淘寶美食 Python3爬蟲三大案例實戰分享
公眾號：Python愛好者社區（微信ID：python_shequ），關注，查看更多連載內容。
加小編個人微信：tsdatajob ，跟作者互動，一起探討。