Leetcode-Question-287: Find the Duplicate Number

原文链接:
https://leetcode.com/problems/find-the-duplicate-number/

题目描述:
287. Find the Duplicate Number
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(n^2).
There is only one duplicate number in the array, but it could be repeated more than once.

解答:

法一: O(n) time, O(1) space,Floyd Cycle Detection,即链表的环检测。参考:
https://leetcode.com/discuss/62696/tortoise-%26-haire-cycle-detection-algorithm

法二:二分法, O(nlogn)的时间复杂度

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注