LeetCode-Python-287. 寻找重复数

90 阅读 0 评论 60 点赞

我是靠谱客的博主心灵美学姐，最近开发中收集的这篇文章主要介绍LeetCode-Python-287. 寻找重复数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

不能更改原数组（假设数组是只读的）。
只能使用额外的 O(1) 的空间。
时间复杂度小于 O(n2) 。
数组中只有一个重复的数字，但它可能不止重复出现一次。

第一种思路：

线性扫描数组，遇到第一个count > 1 的元素就把它返回。

class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for item in nums:
if nums.count(item) != 1:
return item

第二种思路：

比较一下sum（nums）和sum（set（nums））和的差值，然后除以它们俩的长度差，就是那个重复的元素

class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return (sum(nums) - sum(set(nums)))/ (len(nums) - len(set(nums)))

第三种思路：

二分查找，已知所有数字的范围是1-n，就可以把left设为1， right 设为n，mid设为left 和right的中间值，

每次循环，用count记录一下有多少个小于等于mid的值，

如果count <= mid，就代表重复的数字应该不会落在mid左侧的区间内，于是更新left；

反之，就更新right。

class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left, right = 1, len(nums) - 1
while(left < right):
mid = left + (right - left) /2
count = 0
for num in nums:
if num <= mid:
count += 1
# print mid, count
if count <= mid:
left = mid + 1
else:
right = mid
return left

第四种思路：

标记法，把每个元素的值当做指向下个元素的下标指针，因为有重复的元素，所以必然有至少两个元素的值相同，因此它们会指向同一个元素，

所以可以从下标为i = 0的元素开始，依次访问对应的元素nums[i]，然后把nums[i]变成相反数，

如果第一次访问，那么访问到的元素就是正数，

如果不是第一次访问，那么访问到的元素就是负数, 代表i 就是重复的数

在下一次循环前更新 i 为nums[i]。

注意这种方法修改了nums，虽然可以过OJ，但是不符合要求。

class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
i = 0
while(1):
val = nums[i]
if val > 0:
nums[i] = -1 * nums[i]
i = val
else:
return i

第五种思路：

双指针法，把每个元素的值当做指向下个元素的下标指针，问题即可转化为链表的求环问题，

分别设定一个快指针fast，一个慢指针slow，快指针一次走两步，慢指针一次走一步，

如果快慢指针重合了，就代表有环，

此时，如果把fast重置为0，fast和slow每次走一步，那么它们下一次相遇的那个点就是环的起点。

class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
slow, fast = 0, 0
while(1):
slow = nums[slow]
fast = nums[nums[fast]]
# print slow, fast
if slow == fast: # loop exists
fast = 0
while(nums[slow] != nums[fast]):
slow = nums[slow]
fast = nums[fast]
# print slow, fast
return nums[fast]