[leetcode287] Find the Duplicate Number
问题描述：
Find the Duplicate Number
My Submissions <button class="btn btn-default active" type="button">Question</button>
Total Accepted: 11017 Total Submissions: 31520 Difficulty: Hard
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.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Subscribe to see which companies asked this question
算法
数组也是一种映射，将index映射为对应元素。
分析题目，发现所有重复元素都是在1至N的整数，这些整数完全可以作为数组的索引，由此想到龟兔赛跑算法，寻找循环。
具体的龟兔赛跑算法，在维基百科有讲解。
https://en.wikipedia.org/wiki/Cycle_detection
#!usr/bin/env python
#-*- coding:utf-8 -*-
class Solution(object):
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
hare = nums[nums[0]]
turtle = nums[0]
while hare != turtle:
hare = nums[nums[hare]]
turtle = nums[turtle]
turtle = 0
while hare != turtle:
turtle = nums[turtle]
hare = nums[hare]
return hare
神州信息成长空间 150人发布
查看3道真题和解析