LeetCode----Find the Duplicate Number

来源:转载

Find the Duplicate Number

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+1,里面的数都在1和n之间,这样,数组里肯定有一个数是出现两次的。假定只有一个数字重复了,找出那个重复数。

要求:数组不可修改,只读;只能使用常数个空间;算法复杂度要小于O(n^2),即不能暴力;假定那个重复数只有一个,但是可以出现许多次。

这题想了好久没想出来。查看了Discuss才明白。

第一种解法:

使用弗洛伊德循环检测法,记得昨天才写了一题叫Linked List Cycle,这题就是用该检测法写出来的。

思路是,根据数组元素的特点,将数组元素与下标一一映射起来。比如数组是13422,则0对应1,1对应3,2对应4等。这样,如果将这种映射当成链的话,可以顺着下标,下标对应的值,下标对应值的对应下标的值,一直遍历,链中有环,则最后一定会进行循环中,比如对于上面的数组,最后陷入了循环下标2对应值4,下标4对应值2,下标2对应值4,如此循环。

单单找到了循环还不够,我们还需要找到进入循环的那个数字,它才是要找的重复数。可以重新用一个下标为0的值从头开始映射,这样与前面循环中的指针相遇时,找到的就是循环的起点。

代码1:

class Solution(object): def findDuplicate(self, nums):""":type nums: List[int]:rtype: int"""slow, fast = 0, 0while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast:break# fast和slow一定在循环中某点相遇了,但是相遇的点不一定是刚刚进入循环的那个元素,# 需要从0开始继续寻找find = 0while find != slow: slow = nums[slow] find = nums[find]return find


第二种解法:

使用二分法。

代码:

class Solution(object): def findDuplicate(self, nums):""":type nums: List[int]:rtype: int"""l, r = 0, len(nums) - 1while l <= r: mid = l + (r - l) / 2 cnt = 0 for n in nums:if n <= mid: cnt += 1 if cnt > mid:r = mid - 1 else:l = mid + 1return l



分享给朋友:
您可能感兴趣的文章:
随机阅读: