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:
“One of the many reasons for the bewildering and tragic character of human existence is the fact that social organization is at once necessary and fatal. Men are forever creating such organizations for their own convenience and forever finding themselves the victims of their home-made monsters.”
—Aldous Huxley (1894–1963)
“Once Vogue showed two or three dresses for stout women, but we were so shaken by the experience we haven’t repeated it in fifty-seven years. Today ... we must acknowledge that a lady may grow mature, but she never grows fat.”
—Edna Woolman Chase (1877–1957)
“The popularity of that baby-faced boy, who possessed not even the elements of a good actor, was a hallucination in the public mind, and a disgrace to our theatrical history.”
—Thomas Campbell (1777–1844)