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:
“A successful social technique consists perhaps in finding unobjectionable means for individual self-assertion.”
—Eric Hoffer (1902–1983)
“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)
“psychologist
It is through friendships that teenagers learn to take responsibility, provide support, and give their loyalty to non- family members. It is also in teenage friendships that young people find confidants with whom to share thoughts and feelings that they are not comfortable sharing with their parents. Such sharing becomes one of the elements of true intimacy, which will be established later.”
—David Elkind (20th century)