Python面试不修改数组找出重复的数字
作者:宇宙之一粟 时间:2023-08-07 05:04:16
数组中重复的数字
在上一篇博客中剑指Offer之面试题3: 数组中重复的数字中,其实能发现这类题目的关键就是一边遍历数组一边查满足条件的元素。
然后我们在博客?用最复杂的方式学会数组(Python实现动态数组)?这篇博客中介绍了数组这一结构的本质,并自己动手实现了一个动态数组。
今天我们介绍一下另一道来自《剑指Offer》的关于数组的面试题——不修改数组找出重复的数字。
不修改数组找出重复的数字
题目二:不修改数组找出重复的数字
给定一个长度为 n+1 的数组里的所有数字都在 0∼n 的范围内,所以数组中至少有一个数字是重复的。
请找出数组中任意一个重复的数字,但不能修改输入的数组。
样例:
给定长度为8的数组 nums = [2, 3, 5, 4,3, 2, 6,7]
那么输出重复的数字2或者3
思路
首先我们得关注到,题目要求是:不修改数组,然后还是 ?? 返回任意一个重复的数字?? 。所以解题思路相比而言变少了:
1.哈希表:跟上一题一样,本题也可以创建一个哈希表,如果原数组的每个数字第一次出现,就把他放到哈希表中去,即原数组大小为m的数字应该放到哈希表下标为m的位置上。空间复杂度是 $O(n)$ 。
2.二分法:那么有没有不用空间复杂度 $O(n)$ 的算法。假设没有重复数,那么??1~n?? 之间,每个数都只能出现一次。而题目中,这个数组至少有一个数字重复,即出现的次数大于1。
利用二分的思想:把 ??1~n?? 的数字从中间数字 m 开始分为两部分,前一半为 1~ m,后面一半为 ??m+1 ~n???,如果 ??1~m?? 中的数字在数组中出现的次数大于 m,那么这一半必定有重复的数字;
否则,那么另一部分必定含有重复数字。接着我们,继续对含有重复数字的区间一分为二,直到找到重复的数字。
思路一:哈希表
def find_duplicated_num(nums):
"""hash_map"""
hash_map = dict()
for i, val in enumerate(nums):
if val in hash_map:
return val
hash_map[val] = i
return False
思路二:二分法
def reduce_inter(nums2, left, right):
""" """
mid = (left + right) // 2
count = 0
length = len(nums2)
for i in range(length):
if (nums2[i] >= left) and (nums2[i] <= mid):
count += 1
if count > mid - left + 1:
return left, mid
else:
return mid+1, right
def find_duplicated_num2(nums2):
left, right = 1, len(nums2) - 1
while left != right:
left, right = reduce_inter(nums2, left, right)
return left
测试
nums = [2, 3, 5, 4, 3, 2, 6, 7]
# nums_n = [5, 4, 3, 2, 6, 7]
print("思路一测试结果: ", find_duplicated_num(nums))
print("思路二测试结果: ", find_duplicated_num2(nums))
结果
思路一测试结果: 3
思路二测试结果: 3
来源:https://blog.51cto.com/yuzhou1su/5306171
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Go定时器cron的使用详解
用户体验设计何去何从,交互设计师又何去何从?
![](https://img.aspxhome.com/file/UploadPic/20101/11/2009-09-17_01-34s.png)
python爬虫入门教程--优雅的HTTP库requests(二)
CentOS 7上为PHP5安装suPHP的方法(彭哥)
![](https://img.aspxhome.com/file/2023/3/67223_0s.png)
JS限制textarea字数
SQL Server 2008图文安装教程第1/2页
![](https://img.aspxhome.com/file/2023/6/98016_0s.jpg)
python如何调用字典的key
Python正则表达式中group与groups的用法详解
![](https://img.aspxhome.com/file/2023/7/81597_0s.png)
Vue.js结合SortableJS实现树形数据拖拽
![](https://img.aspxhome.com/file/2023/1/130131_0s.png)
python的rllib库你了解吗
Python实现读取文件最后n行的方法
Python实现打乒乓小游戏
![](https://img.aspxhome.com/file/2023/1/105391_0s.gif)
python子类如何继承父类的实例变量
Docker如何部署Python项目的实现详解
![](https://img.aspxhome.com/file/2023/4/124314_0s.png)
OpenCV-Python实现人脸磨皮算法
![](https://img.aspxhome.com/file/2023/5/114735_0s.jpg)
亚马逊购物用户体验分析 (二)
![](https://img.aspxhome.com/file/UploadPic/200910/25/look-inside-75s.jpg)
Go简单实现协程方法
![](https://img.aspxhome.com/file/2023/3/105143_0s.png)
mysql中写判断语句的方法总结
![](https://img.aspxhome.com/file/2023/4/70394_0s.png)
Python中利用aiohttp制作异步爬虫及简单应用
![](https://img.aspxhome.com/file/2023/6/135286_0s.png)
详解python中的defaultdict 默认值
![](https://img.aspxhome.com/file/2023/3/89123_0s.png)