Two algorithms are presented for binding the values that occur more than n ÷ k times in an array b0:n – 1. The second one requires time proportional to n ∗ log(k) and extra space proportional to k. A theorem suggests that this algorithm is optimal among algorithms that are based on comparing array elements. Thus, finding the element that occurs more than n ÷ 2 times requires linear time, while determining whether there is a duplicate – the case k = n – requires time proportional to n ∗ log n.
The algorithms may be interesting from a standpoint of programming methodology; each was developed as an extension of the algorithm for the simple case k = 2.
%0 Journal Article
%1 Misra1982143
%A Misra, J.
%A Gries, David
%D 1982
%J Science of Computer Programming
%K streaming_model
%N 2
%P 143 - 152
%R 10.1016/0167-6423(82)90012-0
%T Finding repeated elements
%V 2
%X Two algorithms are presented for binding the values that occur more than n ÷ k times in an array b0:n – 1. The second one requires time proportional to n ∗ log(k) and extra space proportional to k. A theorem suggests that this algorithm is optimal among algorithms that are based on comparing array elements. Thus, finding the element that occurs more than n ÷ 2 times requires linear time, while determining whether there is a duplicate – the case k = n – requires time proportional to n ∗ log n.
The algorithms may be interesting from a standpoint of programming methodology; each was developed as an extension of the algorithm for the simple case k = 2.
@article{Misra1982143,
abstract = {Two algorithms are presented for binding the values that occur more than n ÷ k times in an array b[0:n – 1]. The second one requires time proportional to n ∗ log(k) and extra space proportional to k. A theorem suggests that this algorithm is optimal among algorithms that are based on comparing array elements. Thus, finding the element that occurs more than n ÷ 2 times requires linear time, while determining whether there is a duplicate – the case k = n – requires time proportional to n ∗ log n.
The algorithms may be interesting from a standpoint of programming methodology; each was developed as an extension of the algorithm for the simple case k = 2.},
added-at = {2013-02-11T02:25:06.000+0100},
author = {Misra, J. and Gries, David},
biburl = {https://www.bibsonomy.org/bibtex/24c4919431d08255a42df059ce9e166f3/ytyoun},
doi = {10.1016/0167-6423(82)90012-0},
interhash = {2d6ed67947c3e8f40732a8b9ce0ceaee},
intrahash = {4c4919431d08255a42df059ce9e166f3},
issn = {0167-6423},
journal = {Science of Computer Programming},
keywords = {streaming_model},
number = 2,
pages = {143 - 152},
timestamp = {2013-02-11T02:25:06.000+0100},
title = {Finding repeated elements},
volume = 2,
year = 1982
}