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:
“Kittering’s brain. What we will he think when he resumes life in that body? Will he thank us for giving him a new lease on life? Or will he object to finding his ego living in that human junk heap?”
—W. Scott Darling, and Erle C. Kenton. Dr. Frankenstein (Sir Cedric Hardwicke)
“A stated truth loses its grace, but a repeated error appears insipid and ridiculous.”
—Johann Wolfgang Von Goethe (1749–1832)
“But all subsists by elemental strife;
And Passions are the elements of Life.”
—Alexander Pope (1688–1744)