Generalization: Finding Repeated Elements
Elements that occur more than n/k times in a multiset of size n may be found in time O(n log k). The element distinctness problem is a special case of k=n. This algorithm is optimal under the decision tree model of computation.
The algorithm is a generalization of the one for a special case of k=2, which had a rather convoluted history of publication.
The above algorithms rely only on the test of identity of the elements. If sorting is allowed, previously known order statistics finding algorithms may be exploited. For example, for k=2, a median may be found first in linear time, and then it may be easily tested whether there are more than n/2 median elements. However the above algorithms require fewer comparisons than the order statistics algorithms.
Read more about this topic: Element Distinctness Problem
Famous quotes containing the words finding, repeated and/or elements:
“If everybody is looking for it, then nobody is finding it. If we were cultured, we would not be conscious of lacking culture. We would regard it as something natural and would not make so much fuss about it. And if we knew the real value of this word we would be cultured enough not to give it so much importance.”
—Pablo Picasso (1881–1973)
“Lift not thy spear against the Muses’ bower:
The great Emathian conqueror bid spare
The house of Pindarus, when temple and tower
Went to the ground; and the repeated air
Of sad Electra’s poet had the power
To save the Athenian walls from ruin bare.”
—John Milton (1608–1674)
“Nature confounds her summer distinctions at this season. The heavens seem to be nearer the earth. The elements are less reserved and distinct. Water turns to ice, rain to snow. The day is but a Scandinavian night. The winter is an arctic summer.”
—Henry David Thoreau (1817–1862)