剑指offer 面试3题
2024-09-04 14:02:04
面试3题:
题:数组中重复的数字
题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
解题思路一:先把输入数组排序,然后从排序后的数组中从前往后找。
解题代码:
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if numbers==None or len(numbers)<=1:
return False
for i in range(len(numbers)):
if numbers[i]<0 or numbers[i]>len(numbers)-1:
return False numbers.sort()
for i in range(len(numbers)-1):
if numbers[i]==numbers[i+1]:
duplication[0]=numbers[i]
return True
return False
解题思路二:使用辅助空间:哈希表。时间复杂度为O(n),空间复杂度为O(n)
解题代码:
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if numbers==None or len(numbers)<=1:
return False usedDic=set() #集合
for i in range(len(numbers)):
if numbers[i]<0 or numbers[i]>len(numbers)-1:
return False
if numbers[i] not in usedDic:
usedDic.add(numbers[i])
else:
duplication[0]=numbers[i]
return True
return False
解题思路三:重排数组:从头到尾扫描数组的每个数字,当扫描到下标为i的数字时,首先比较这个数字(假设为m)是否等于i,如果是,接着扫描下一个数字;如果不是,那么再将它和下标为m的数字对比,如果两者不相等,就把它和第m个数字交换,把m放到属于它的位置,如果两者相等,那么就找到了一个重复的数字。重复这个过程,知道发现一个重复的数字。
解题代码:(根据代码分析复杂度:所有操作都在输入数组上进行,不需要额外分配空间,因此空间复杂度为O(1);尽管代码中有一个两重循环,但是每个数字最多只要交换两次就能找到它自己的位置,因为总的时间复杂度为O(n))
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if numbers==None or len(numbers)<=1:
return False for i in range(len(numbers)):
if numbers[i]<0 or numbers[i]>len(numbers)-1:
return False for i in range(len(numbers)):
while (numbers[i]!=i):
if numbers[i]==numbers[numbers[i]]:
duplication[0]=numbers[i]
return True
else:
temp=numbers[i]
numbers[i]=numbers[temp]
numbers[temp]=temp
return False
拓展:不修改数组找出重复的数字。
'''
拓展:不修改数组找出重复的数字。
在一个长度为n+1的数组里的所有数字都在1~n的范围内,所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字,
但不能修改输入的数组,例如输入长度为8的数组[2,3,5,4,3,2,6,7],那么对应的输出是重复的数字为2或3。
''' # 方法一:利用哈希表,时间复杂度O(n),空间复杂度O(n)
# 方法二:二分查找的变形,如下,时间复杂度O(nlogn),空间复杂度为O(1) class Solution:
def duplicate(self, numbers):
# write code here
if not numbers or len(numbers)<=0:
return -1
start=1
end=len(numbers)-1
while start<=end:
middle=(end-start)//2+start
count=self.countRange(numbers,len(numbers),start,middle)
if end==start:
if count>1:
return start
else:
break
if count>middle-start+1:
end=middle
else:
start=middle+1
return -1 def countRange(self,numbers,length,start,end):
'''
计算数组中的元素大于等于start,小于等于end的元素的个数
'''
if not numbers:
return 0
count=0
for i in range(length):
if numbers[i]>=start and numbers[i]<=end:
count+=1
return count if __name__=="__main__":
print(Solution().duplicate([2,3,5,4,3,2,6,7]))
最新文章
- Mono Fragment之间转换
- Angular中的Error: [$resource:badcfg]错误如何解决之一种
- Redis 笔记与总结4 set 和 zset 类型
- 使用Spring的命名空间p装配属性-摘自《Spring实战(第3版)》
- bzoj1036: [ZJOI2008]树的统计Count 树链剖分+线段树
- Spring MVC Framework 注解
- C++中枚举定义运算符
- android多国语言文件夹
- Android游戏开发之旅 View类详解
- 【原创】大叔问题定位分享(23)Ambari安装向导点击下一步卡住
- ubuntu上传到百度网盘
- Nginx的特性与核心类别及配置文件和模块详解
- jsoi r2d1t3的50分
- b4和tncl_extract_UNCL_new
- bzoj1043 [HAOI2008]下落的圆盘
- Build Tree View Structure for SharePoint List Data
- 【jQuery】todolist
- ZT linux 线程私有数据之 一键多值技术
- 如何ping测有端口的网站
- 【ospf-链路验证】