Python学习之妙用字典类型

落日映苍穹つ 2022-12-19 03:45 157阅读 0赞

从一道leetcode题目说起，题目链接：

https://leetcode.com/problems/contains-duplicate-ii/

题目描述如图：

![format_png][]

题目很简单，理解起来也很容易，给定一个数据nums，判断是否存在这样的k索引i和j，使得nums\[i\] == nums\[j\] 且 j - i >= k，nums，k为给定的值，0<=i<=j < length，理解意思之后很容易就写出这样的代码：

class Solution:
        def containsNearbyDuplicate(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
            for i in range(len(nums)):
                if nums[i] in nums[i+1:i+k+1]:
                    return True
            return False

我这里的思路就是直接判断 nums\[i\] 这个值是否在 切片数组nums\[i+1:i+k+1\]里面，存在则返回True，不存在则返回False，因为Python列表切片不涉及到越界的问题，所以不用去判断数组(列表)长度。

![format_png 1][]

也许你会想，这也太简单了，满怀欣喜的提交，却发现 超时了。

![format_png 2][]

啊。。。。。。。。。这样的是不行的，无法通过测试，那只能换一种思路了。

我们知道，Python中list对象的存储结构采用的是线性表，采用 in 这样的方式查询元素的时间复杂度是 O(n),上面的程序总的时间复杂度是O(n\*k)(n表示数组长度),因此在给定的数组比较大时，会导致超时，其消耗的时间也就在于查询元素。

那有没有更快的方式的呢？有的，我们可以使用 字典类型，它查询元素的时间在最优的情况下可以达到O(1)，也就是基本不用花什么时间就能取得元素。那这样整体换算下来，程序的时间就只有O(n)

思路：新建一个字典类型，用key来保存 数组元素值，用value来保存索引值，类似哨兵的效果，即查询到元素在字典中存在时，这时新的索引减去旧的索引，如果小于给定的K值，则返回True，否则更新元素的索引值，直到访问完所有元素，代码如下：

class Solution(object):
        def containsNearbyDuplicate(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
            d = {}
            for i,num in enumerate(nums):
                if num in d:
                    if i - d[num] <= k:
                        return True
                d[num] = i
            
            return False

再次提交，Accepted了，再也不会超时了，而且还发现这种方法居然打败了99.95%的用户。赞！

Python真是一门不掉头发的语言啊！

[format_png]: /images/20221120/435b777904d34265a270024d1c4eec13.png
[format_png 1]: /images/20221120/a06ecd1057e8401aa9ab478ff42e5981.png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9MbGw4dHgwTURSMDI3NkdTM29ac0szMGljcFByeWlheG5ZMGRHWjJuOFYzaWI1SGZMdnVyY2ljUGZXZEtOQlQ4V2FBcFpwQm9CV2cxRGJ0TzlETWRuNXFpYm1RLzY0MA?x-oss-process=image/format,png