咨询你github上leetcode 220题的第一种解法

Question

请问老师第220题，这题第一种解法为什么用set，而不用unorded_set，是因为unorder_set中没有lower_bound这个函数吗？一定要有序吗？另外如果是一样的元素岂不是会覆盖set里已有的那个元素吗？这样有影响吧？

Answer 1

liuyubobobo 2019-02-28 02:42:57

1）对，第一种方法使用set是因为有lower_bound，因为set本质是二分搜索树（红黑树），所以可以在logn的时间内查找到树中某一个数据的前驱或者后继。否则应该会超时。

2）整个算法的record中，存储了距离当前考察的元素（i）为k的所有元素。（33，34行在维护着一点），所以，如果在这个距离范围内有重复值，说明他们的差值为0，肯定满足任意给定的t。所以，在这个范围里，有重复值，我们直接就返回true了（一定满足27行的判断）：）自己针对有重复值的测试用例，实际运行这个程序，使用debug的方式一步一步跟踪，看一看程序是怎么处理的？：）

3）也可以自己尝试使用unordered_set，按照你的思路实现一下试试看？看是否可以，会有什么问题？（可能是可以完成的，届时分享一下你的想法：））

加油！：）

Answer 2

提问者 stoneboy100200 2019-02-28 23:01:42

感谢波波老师的及时答复，我试了用unordered_set确实找不到lower_bound这个函数，想知道为什么lower_bound这个函数一定要在排好序的元素中才能使用呢？是不是不排序的话用不了吗？

• liuyubobobo #1

  是。lower_bound使用logn的复杂度寻找后继，只有搜索树上可以有这样的效率。在非搜索树上，你可以直接写一个O(n)的扫描一遍：）

• 提问者 stoneboy100200 回复 liuyubobobo #2

  感谢波波老师这么及时的回复，另外询问下老师有讲深度学习的课程吗？高等数学微积分和概率统计有吗？

• liuyubobobo 回复 提问者 stoneboy100200 #3

  暂时我都没有。但慕课网有。我的所有课程可以参考https://www.imooc.com/u/108955 加油！：）