每日一题20201202(217. 存在重复元素)

小克klose · · 445 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

217. 存在重复元素

image-20201202135946680

思路

首先,要确定一个元素是否出现多次,那么肯定O(n)的复杂度是少不了的,因为肯定需要一次遍历.

一次遍历的话,还需要记住每个数字出现的次数,所以可以考虑用hash表记录数字出现的数字。

看了题解也没有更好的解法了,暴力法更是O(n²)的复杂度,还有一种排序后遍历,复杂度也很高。

golang解法

func containsDuplicate(nums []int) bool {
    hash := make(map[int]int)
    for _, n := range nums {
        hash[n] += 1
        if hash[n] > 1 {
            return true
        }
    }
    return false
}
image-20201202140410924

Python解法 set

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return not len(nums) == len(set(nums))
image-20201202140542147

Python hash表

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        mp = dict()
        for n in nums:
            mp[n] = mp.get(n, 0) + 1
            if mp[n] > 1:
                return True
        return False
image-20201202140749718

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:小克klose

查看原文:每日一题20201202(217. 存在重复元素)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

445 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传