凡科网站后台登陆,指数运算法则,服务器重启后网站打不开,杭州房产网二手房寻找重复数字
287. 寻找重复数
题目难度
中等
相关标签与企业信息
[相关标签] [相关企业]
题目描述
给定一个包含 n 1 n 1 n1 个整数的数组 nums#xff0c;其数字都在 [ 1 , n ] [1, n] [1,n] 范围内#xff08;包括 1 1 1 和 n n n#xff09;#xff0c;可…寻找重复数字
287. 寻找重复数
题目难度
中等
相关标签与企业信息
[相关标签] [相关企业]
题目描述
给定一个包含 n 1 n 1 n1 个整数的数组 nums其数字都在 [ 1 , n ] [1, n] [1,n] 范围内包括 1 1 1 和 n n n可知至少存在一个重复的整数。
假设 nums 只有一个重复的整数返回这个重复的数。
你设计的解决方案必须不修改数组 nums 且只用常量级 O ( 1 ) O(1) O(1) 的额外空间。
示例
示例1
输入nums [1, 3, 4, 2, 2] 输出2
示例2
输入nums [3, 1, 3, 4, 2] 输出3
示例3
输入nums [3, 3, 3, 3, 3] 输出3
提示信息 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1≤n≤105nums.length n 1 1 ≤ n u m s [ i ] ≤ n 1 \leq nums[i] \leq n 1≤nums[i]≤nnums 中只有一个整数出现两次或多次其余整数均只出现一次。
进阶问题
如何证明 nums 中至少存在一个重复的数字
根据抽屉原理鸽巢原理将 n 1 n 1 n1 个元素放到 n n n 个集合中那么至少有一个集合里面会有两个或更多的元素。
在本题中数组 nums 有 n 1 n 1 n1 个整数而这些整数的取值范围是 [ 1 , n ] [1, n] [1,n]相当于把 n 1 n 1 n1 个“鸽子”放进 n n n 个“鸽巢”数字 1 1 1 到 n n n 所代表的 n n n 个区间所以必然至少存在一个数字是重复的。
比如一个训练营里面有367人则必然至少有 两个人生日同一天。
你可以设计一个线性级时间复杂度 O ( n ) O(n) O(n) 的解决方案吗
解题思路
方法一快慢指针类似环形链表找环入口
把数组 nums 中的值看作是下一个节点的索引这样整个数组就可以看作是一个类似链表的结构。由于存在重复的数字那么必然会形成一个“环”因为从某个重复数字开始会再次指向已经访问过的节点也就是这个重复数字本身对应的下一个节点。我们可以使用快慢指针的方法来找到这个环的入口也就是重复的数字。复习链表找环这个也太难想到了吧没想到这里遇到了环形链表
该思路主要是通过将数组视为特殊链表结构来解决寻找重复数的问题具体如下
整体思路转化
把给定的数组 nums 中的值当作指向下一个链表节点的索引从而将寻找数组中重复数字的问题转化为在类似链表结构中寻找环的起点的问题因为存在重复数字时会形成环。
快慢指针运用
初始化设置 slow 指针指向数组第一个节点nums[0]fast 指针指向第二个节点nums[nums[0]]。找环过程通过循环让快慢指针移动slow 每次按当前节点值作为索引移动一步fast 每次先根据当前节点值作为索引找到下一个节点再以该节点值作为索引移动两步。由于 fast 速度是 slow 的两倍在有环情况下它们必然会在环内相遇。确定重复数当快慢指针相遇后设置一个新指针如代码中的 pre从链表起点出发与在环内相遇的 slow 指针同步移动每次按节点值作为索引前进。由于从链表起点到环入口的距离和从相遇点到环入口的距离相等所以它们再次相遇的点就是环的入口即数组中的重复数字。
class Solution:def findDuplicate(self, nums: List[int]) - int:# 将该数组视为链表数组上的值视为指向下一个链表节点的索引# 将“寻找数组重复数”的问题转变成了“寻找链表环的起点(已经解决)”# 寻找链表环起点 ## 快慢指针找环## 若相遇f走了2xs走了x假设s在环内走了t环外链表长x-t## 此时 head走x-t到入口s走x-t也回到入口# 初始化快慢指针slow 第一个节点fast 第二个节点[第一个节点值作为索引]slow, fast nums[0], nums[nums[0]]# 判断有无环while逻辑没走到终点就一直走# while nums[slow] and !!!这道题不需要判断默认输入必有环# 所以直接开始找环# 第一次进入环while slow ! fast:slow nums[slow]fast nums[nums[fast]]# 退出以上while的条件是实现了s和f指针的第一次相遇# 此时将其中一个指针退回到起点或者设置一个起点指针pre 0# 设置pre和s同步走相遇点就是环入口就是重复数while pre ! slow:slow nums[slow]pre nums[pre]return slow
以下是对上述用于寻找数组重复数的代码的时空复杂度分析
时间复杂度 整体分析思路时间复杂度主要取决于代码中循环语句的执行次数。在这段代码中有两个主要的 while 循环我们分别来分析它们对时间复杂度的影响。 第一个 while 循环快慢指针找环 在这个循环中slow 指针和 fast 指针在类似链表的结构中移动直到它们相遇。由于 fast 指针每次移动的速度是 slow 指针的两倍所以在最坏的情况下fast 指针需要绕环两圈才能和 slow 指针相遇可以想象成在一个环形跑道上快跑的人要追上慢跑的人最多跑两圈就能追上。而对于整个数组 nums 所构成的类似链表结构其长度为 n 1题目中给定数组包含 n 1 个整数。即使在最坏的情况下fast 指针绕环两圈它总共走过的节点数也不会超过数组长度的两倍也就是 O(2(n 1))根据大O表示法的特性常系数可以忽略所以这个循环的时间复杂度为 O(n)其中 n 是数组 nums 的长度准确来说是 n 1但在大O表示法中可以近似看作 n。 第二个 while 确定环入口即重复数 当快慢指针相遇后新设置的指针如代码中的 pre和在环内相遇的 slow 指针同步移动直到它们再次相遇找到环的入口也就是重复的数字。在这个过程中这两个指针最多需要遍历整个数组长度的节点数因为从它们开始同步移动到相遇所走过的路径长度不会超过数组所构成的类似链表结构的总长度。所以这个循环的时间复杂度同样为 O(n)其中 n 是数组 nums 的长度。 综合时间复杂度由于整个代码的执行时间主要由这两个 while 循环决定并且它们的时间复杂度都是 O(n)所以这段代码的总体时间复杂度为 O(n)。
空间复杂度 分析思路空间复杂度主要看代码在执行过程中额外开辟的空间大小与输入数据的规模无关。 代码中的空间使用情况在这段代码中除了定义了几个指针变量如 slow、fast、pre来辅助完成算法逻辑外并没有使用额外的数据结构来存储数据。这些指针变量所占用的空间是固定的不随输入数组的长度 n 而变化。 空间复杂度结论所以根据空间复杂度的定义这段代码的空间复杂度为 O(1)即只使用了常量级别的额外空间满足题目要求不使用超过常量级 O(1) 的额外空间来解决问题。
综上所述这段代码的时间复杂度为 O(n)空间复杂度为 O(1)。
方法二二分查找
为什么可以通过 mid中间值和 count小于等于中间值的数字个数的大小关系来判断重复数字所在的区间。
整体思路
我们的目标是在数组 nums 中找到那个重复的数字已知数组中的数字范围是 [1, n]且只有一个数字是重复的。我们通过不断二分这个范围 [1, n]并根据 count 和 mid 的关系来逐步缩小重复数字可能存在的区间。
具体解释
假设当前我们正在考虑的范围是 [left, right]在代码中最初就是 [1, len(nums) - 1]随着循环不断更新 left 和 right然后我们计算出了这个区间的中间值 mid。
接下来我们统计数组 nums 中小于等于 mid 的数字个数记为 count。 当 count mid 时 正常情况下如果数组中的数字没有重复那么在范围 [1, mid] 内的数字应该恰好出现 mid 次因为每个数字只出现一次嘛。但现在我们统计出来的 count 大于 mid这就意味着在 [1, mid] 这个区间内的数字出现的次数比正常情况多了。为什么会多呢只能是因为那个重复的数字在这个区间内呀所以重复的数字肯定在 [1, mid] 这个区间我们就可以把查找范围的上界 right 更新为 mid下一次就在缩小后的范围 [1, mid] 内继续查找。 当 count mid 时 同样如果数字没有重复在范围 [1, mid] 内的数字应该恰好出现 mid 次。现在 count 不大于 mid说明在 [1, mid] 这个区间内的数字出现的次数是正常的或者更少那就意味着重复的数字不在这个区间内而是在 [mid 1, right] 这个区间里所以我们就把查找范围的下界 left 更新为 mid 1下一次就在缩小后的范围 [mid 1, right] 内继续查找。
通过这样不断地根据 count 和 mid 的关系来更新查找范围最终就能确定重复数字所在的区间当查找范围缩小到只剩下一个数字时这个数字就是我们要找的重复数字啦。
例如假设有数组 [3, 1, 3, 4, 2]我们来模拟一下这个过程
初始时left 1right 4因为数组长度是 5数字范围是 [1, 4]计算出 mid 2。统计数组中小于等于 2 的数字个数 count发现有 2 个1 和 2此时 count mid说明重复数字不在 [1, 2] 区间我们就把 left 更新为 3。下一次循环left 3right 4计算出 mid 3再统计小于等于 3 的数字个数发现有 3 个312此时 count mid说明重复数字在 [1, 3] 区间我们就把 right 更新为 3。此时 left right 3所以重复数字就是 3。
希望这样解释能让你清楚理解 mid 和 count 的关系以及为什么可以通过它们来判断重复数字的位置。
最关键的一步是mid与count的比较照理来说count就是该比mid小 只要大了就在这个范围内
方法二二分查找
def findDuplicate(nums):low 1high len(nums) - 1while low high:mid low (high - low) // 2count 0for num in nums:if num mid:count 1if count mid:high midelse:low mid 1return low测试用例
测试用例1
输入nums [1, 3, 4, 2, 2] 预期输出2
测试用例2
输入nums [3, 1, 3, 4, 2] 预期输出3
测试用例3
输入nums [3, 3, 3, 3, 3] 预期输出3
测试用例4
输入nums [1, 2, 3, 4, 4] 预期输出4
测试用例5
输入nums [2, 2, 2, 2, 2] 预期输出2
测试结果
方法一快慢指针
测试用例1通过输出为2。测试用例2通过输出为3。测试用例3通过输出为3。测试用例4通过输出为4。测试用例5通过输出为2。
方法二二分查找
测试用例1通过输出为2。测试用例2通过输出为3。。测试用例3通过输出为3。测试用例4通过输出为4。测试用例5通过输出为2。
通过对多种测试用例的测试两种方法都能正确地找出数组中重复的数字满足题目要求。
