Leetcode Find the Duplicate Number
2024-10-11 20:23:56
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2)
. - There is only one duplicate number in the array, but it could be repeated more than once.
最容易想到的思路是新开一个长度为n的全零list p[1~n]。依次从nums里读出数据,假设读出的是4, 就将p[4]从零改成1。如果发现已经是1了,那么这个4就已经出现过了,所以他就是重复的那个数。这个解法的时间复杂度是O(N)。但是由于本题要求空间复杂度是O(1)。所以不能用。
可以用二分法,low = 1, high = n, mid = (left + right)//2,如果<=mid 的元素个数 > mid,那么重复的数字一定在[1, mid]区间内。反之,则一定在[mid+1, high]里面。注意红色的>mid不能是>=。
例如 【1,2, 2, 3(mid), 4, 5, 6】,【1,2, 3, 3(mid), 4, 5】
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left = 1
right = len(nums) - 1 while left < right:
mid = (left + right)//2
count = 0
for x in nums:
if x <= mid:
count += 1 if count > mid:
right = mid
else:
left = mid + 1 return left
第二种解法来自:http://www.cnblogs.com/grandyang/p/4843654.html
使用类似Linked List Cycle II的思路。
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
slow = 0
fast = 0
t = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
while True:
slow = nums[slow]
t = nums[t]
if slow == t:
break
return slow
最新文章
- 《ASP.NET SignalR系列》第三课 SignalR的支持平台
- Web SQL数据库
- css改变背景透明度【转】
- JAVA语法细节(1)
- 对ASP.NET Entity FrameWork进行单元测试
- 【html5】这些新类型 能提高生产力
- AbStract 和Interface 方法是否能用Static修饰,为什么?
- Delphi ADOQuery的速度优化 转
- 设置imageView正方形高宽
- VBA读取word中的内容到Excel中
- HDU 4284 状压dp+spfa
- 阿里安全潘多拉实验室首先完美越狱苹果iOS 11.2
- C语言第二周作业
- idea+maven下jrebel的安装破解
- KakfaSpout自定义scheme
- HTTP协议详细分析
- C# Parallel并发执行相关问题
- 基于SOUI开发一个简单的小工具
- 微信公众号自定义菜单中添加emoji表情
- python 无序表查找
热门文章
- mysql连接数设置操作(Too many connections)
- PAT 1027. 打印沙漏(20)
- Java集合系列:-----------08HashMap的底层实现
- windows mysql提示:1045 access denied for user &#39;root&#39;@&#39;localhost&#39; using password yes 解决方案
- Spring TestContext测试框架搭建
- 【福吧资源网整理】老男孩-python运维6期 不加密
- 文本比较算法Ⅱ——Needleman/Wunsch算法
- unity3d 音频无缝循环
- .Net分布式异常报警系统-客户端及服务端API
- 欧几里德与扩展欧几里德算法 Extended Euclidean algorithm