剑指offer-开启美(刷)好(题)生活:第一题,找出数组中重复的数字

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

## **本文结构** --- ### **1. 题库链接** ### **2. 题目名称 ** ### **3. 题目描述** ### **4. 解题思路** ### **5. 解法代码** ### **6. 解法分析** ### **7. 疑问困惑** --- ### 1. 题库链接 https://www.acwing.com/problem/,搜索“剑指offer”。 --- ### 2. 题目名称 找出数组中重复的数字。 --- ### 3. 题目描述 给定一个长度为 n 的整数数组 nums,数组中所有的数字都在 0∼n−1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 **注意:如果某些数字不在 0∼n−1的范围内,或数组中不包含重复数字,则返回 -1。** **样例:**给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。返回 2 或 3。 --- ### 4. 解题思路 利用map,将数组nums中的元素值作为key,此元素出现的次数作为value,构造一个map。遍历数组nums,判断map[key]是否存在。如果存在,则将此key出现次数加1;反之,将此key出现次数置为1。 --- ### 5. 解法代码 ```go func duplicateInArray(nums []int) int { var duplicateMap map[int]int var arrLen = len(nums) duplicateMap = make(map[int]int, arrLen) for _, value := range nums { if value < 0 || value > arrLen - 1{ return -1 } if v, ok := duplicateMap[value]; ok { duplicateMap[value] = v + 1 } else { duplicateMap[value] = 1 } } for k, v := range duplicateMap { if v > 1 { return k } } return -1 } ``` --- ### 6、解法分析 对于算法复杂度分析,一直不在行。这里尝试分析一波,请大牛指点一下。 ```go for _, value := range nums { if value < 0 || value > arrLen - 1{ return -1 } if v, ok := duplicateMap[value]; ok { duplicateMap[value] = v + 1 } else { duplicateMap[value] = 1 } } ``` 这个循环的时间复杂度应该是O(n)。 ```go for k, v := range duplicateMap { if v > 1 { return k } } ``` 这个循环的时间复杂度应该最坏情况下是:O(n),最好情况下是:O(1)。 所以整个算法的时间复杂度是:O(n)。 不知道这样分析对不对。 算法的空间复杂度是:O(n)。因为需要分配一个大小为n的map作为额外空间使用。 --- ### 7、疑问困惑 1、解法分析中关于时间复杂度和空间复杂度的困惑,请大牛帮忙指点一下,我分析的对不对。 2、此题目还有没有更好的解决方法。

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

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

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