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:
“There is no rule more invariable than that we are paid for our suspicions by finding what we suspected.”
—Henry David Thoreau (1817–1862)
“A stated truth loses its grace, but a repeated error appears insipid and ridiculous.”
—Johann Wolfgang Von Goethe (1749–1832)
“A party of order or stability, and a party of progress or reform, are both necessary elements of a healthy state of political life.”
—John Stuart Mill (1806–1873)