StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I have outlined a way based on the Boyer-Moore majority voting algorithm <a href="https://stackoverflow.com/a/8206433/1011995">here</a>.</p> <p>You remember (up to) <code>(m-1)</code> elements that have recently been more often seen than the others and associated counts. When a remembered element is seen, its count is increased. When a not-remembered element is seen, if there is a slot free, you remember it and set its count to 1, otherwise you subtract 1 from all counts of the remembered elements. A remembered element whose count goes to 0 is forgotten. Any element occurring with a higher proportion than <code>1/m</code> is one of the remembered elements. If you do not know a priori that there are <code>m-1</code> elements occurring more than <code>n/m</code> times, you need a second pass to count the occurrences of the remembered elements.</p> <p><strong>Edit:</strong> After visiting the indicated page, I see it is the exact same solution, except it doesn't account for remembered non-dominants.</p> <blockquote> <p>Once this has been finished any count variables with counts greater than 1 have more than 10 instances of themselves in the list.</p> </blockquote> <p>is not correct, but all decimal dominants will be remembered with a count <code>>= 1</code> at the end. I haven't gone through the code there, so it may contain errors, but the algorithm is correct, except for the missing checking pass. </p> <p>The proposed counterexample is dealt with correctly if we have the second pass, the state evolves</p> <pre><code>0 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 // coming 9 0 0 0 0 0 0 0 0 0 // all forgotten, no slots occupied, coming 10 10 - - - - - - - - 1 - - - - - - - - // coming 0 10 0 - - - - - - - 1 1 - - - - - - - </code></pre> <p>at the end, there are two slots occupied, 10 and 0 are both remembered with a count of 1. 10 isn't a decimal dominant, but 0 is, and it is the only one, as will be verified by the second checking pass.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload