ONLamp.com -- Numerical Python Basics
Finding Duplicate Elements in an Array :: Phil! Gregory Annotated
- Interesting way to find duplicates in an array. Enjoyed the links on the pigeonhold principle and Floyd's cycle-finding algorithm.
- post by taylortree
Now, suppose that the array is of length n and only contains positive
integers less than n. We can be sure (by the pigeonhole principle)
that there is at least one duplicate.
integers less than n. We can be sure (by the pigeonhole principle)
that there is at least one duplicate.
So, how do we find the beginning of the cycle? The easiest approach is to
use Floyd's cycle-finding algorithm. It works roughly like this:
Start at the beginning of the sequence. Keep track of two values (call
them ai and aj). At
each step of the algorithm, move ai one step
along the sequence, but move aj two steps. Stop
when ai = aj.
use Floyd's cycle-finding algorithm. It works roughly like this:
Start at the beginning of the sequence. Keep track of two values (call
them ai and aj). At
each step of the algorithm, move ai one step
along the sequence, but move aj two steps. Stop
when ai = aj.
- post by taylortree