StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I assume:</p> <ol> <li>The elements of the array are comparable. </li> <li>We know the values of n and k beforehand.</li> <li>A solution O(n*k+b) is good enough.</li> </ol> <p>Let the number occuring only b times be S. We are trying to find the S in an array of n*k+b size.</p> <p><strong>Recursive Step:</strong> Find the median element of the current array slice as in Quick Sort in lineer time. Let the median element be M. </p> <p>After the recursive step you have an array where all elements smaller than M occur on the left of the first occurence of M. All M elements are next to each other and all element larger than M are on the right of all occurences of M. </p> <p>Look at the index of the leftmost M and calculate whether S<M or S>=M. Recurse either on the left slice or the right slice.</p> <p>So you are doing a quick sort but delving only one part of the divisions at any time. You will recurse O(logN) times but each time with 1/2, 1/4, 1/8, .. sizes of the original array, so the total time will still be O(n).</p> <p><strong>Clarification:</strong> Let's say n=20 and k = 10. Then, there are 21 distinct elements in the array, 20 of which occur 10 times and the last occur let's say 7 times. I find the medium element, let's say it is 1111. If the S<1111 than the index of the leftmost occurence of 1111 will be less than 11*10. If S>=1111 then the index will be equal to 11*10.</p> <p><strong>Full example:</strong> n = 4. k = 3. Array = {1,2,3,4,5,1,2,3,4,5,1,2,3,5} After the first recursive step I find the median element is 3 and the array is something like: {1,2,1,2,1,2,3,3,3,5,4,5,5,4} There are 6 elements on the left of 3. 6 is a multiple of k=3. So each element must be occuring 3 times there. So S>=3. Recurse on the right side. And so on.</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