从两道亦可赛艇的算法题看字典的神奇作用

作者：侯正平

字典是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): cowdict={} cowdictnum = {} maxid = -1 for i in range(len(cowlist)): if cowdict.get(cowlist[i]) is None: cowdict[cowlist[i]] = i else: if i - cowdict[cowlist[i]] <= k: maxid = max(maxid,cowlist[i]) else: cowdict[cowlist[i]] = i return(maxid)

测试结果

综上，引入字典其实是一种典型的用空间换速度的策略，希望这两道题目对读者有所启发，当然，如果文中有不当之处，或者有更好的方法，也欢迎指出。

福利：文末扫码立刻关注公众号，“Python爱好者社区”，开始学习Python课程：

关注后在公众号内回复“课程”即可获取：

1.崔老师爬虫实战案例免费学习视频。

2.丘老师数据科学入门指导免费学习视频。

3.陈老师数据分析报告制作免费学习视频。

4.玩转大数据分析！Spark2.X+Python 精华实战课程免费学习视频。

5.丘老师Python网络爬虫实战免费学习视频。