首页 > 代码库 > Leetcode Find the Duplicate Number

Leetcode Find the Duplicate Number

2024-08-27 12:06:01   216人阅读

最容易想到的思路是新开一个长度为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】 

 1 class Solution(object):
 2     def findDuplicate(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         left = 1
 8         right = len(nums) - 1
 9         
10         while left < right:
11             mid = (left + right)//2
12             count = 0
13             for x in nums:
14                 if x <= mid:
15                     count += 1
16             
17             if count > mid:
18                 right = mid 
19             else:
20                 left = mid + 1
21         
22         return left

第二种解法来自：http://www.cnblogs.com/grandyang/p/4843654.html

使用类似Linked List Cycle II的思路。

 1 def findDuplicate(self, nums):
 2         """
 3         :type nums: List[int]
 4         :rtype: int
 5         """
 6         slow = 0
 7         fast = 0
 8         t = 0
 9         while True:
10             slow = nums[slow]
11             fast = nums[nums[fast]]
12             if slow == fast:
13                 break
14         while True:
15             slow = nums[slow]
16             t = nums[t]
17             if slow == t:
18                 break
19         return slow

 

Leetcode Find the Duplicate Number


联系
我们