287. Find the Duplicate Number (floyd判圈算法找重复元素)

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:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n<sup>2</sup>).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

思路:O(n^2)的复杂度暴力即可,说个O(n)复杂度的解法。

需要注意元素范围1..n是个很重要的条件。

使得我们可以把位置和元素映射起来。

可以看成一个迭代函数

由于存在重复重复元素,因此一定存在一个环。

因此可以用floyd判圈算法。

floyd判圈算法_维基百科

这算法以前遇到过sgu455 解题报告,所以不算很陌生…

但是从有重复元素没有联想到会有环orz,我好菜啊…

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz