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:
“I do not know what I may appear to the world; but to myself I seem to have been only like a boy playing on the seashore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me.”
—Isaac Newton (1642–1727)
“When we awoke, we found a heavy dew on our blankets. I lay awake very early, and listened to the clear, shrill ah, te te, te te, te of the white-throated sparrow, repeated at short intervals, without the least variation, for half an hour, as if it could not enough express its happiness. Whether my companions heard it or not, I know not, but it was a kind of matins to me, and the event of the forenoon.”
—Henry David Thoreau (1817–1862)
“The elements of success in this business do not differ from the elements of success in any other. Competition is keen and bitter. Advertising is as large an element as in any other business, and since the usual avenues of successful exploitation are closed to the profession, the adage that the best advertisement is a pleased customer is doubly true for this business.”
—Madeleine [Blair], U.S. prostitute and “madam.” Madeleine, ch. 5 (1919)