Databases
StackOverflow2013
Postsdbo
POSublinear algorithm / find the last of distinct elements
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSublinear algorithm / find the last of distinct elements
    text
    copied!<p>Background in case you care, if not skip it:</p> <p>I was recording some audio today for a project, doing it a paragraph at a time. If I messed up the paragraph, I redid it until I got it right, and then moved on the next paragraph. When I loaded them onto the computer, I needed to find the last recording for each paragraph. Without any knowledge of the number of recordings I made for a particular paragraph, how do I go about this? (Don't you love it when algorithms sneak up into your daily life?)</p> <p>In algorithms terms, you have an array of elements, where each element is either followed by another element of the same type, or a completely different element. Find each last element of the sequence (the audio clip correctly recorded).</p> <p><strong>The problem:</strong></p> <p>So you have an array of objects where each element with an id field, where each id is in the following list. I want the objects that are the last of their id, say in array of id's like this:</p> <pre><code>aabbbbbccddddddddddddddeefffffffffggghhhhiiiijjklmnnnnoo </code></pre> <p>Obviously if the length of the string is n and there are n distinct elements, it will take you n steps to figure it out. I'm more interested in the general algorithm. I could do it with a binary search type algorithm, but I don't know the runtime of it in the case with no knowledge of the input except the number of total elements.</p> <p>Also, would knowing the number of distinct id's change the runtime of the algorithm? This is an interesting problem to me and I'm asking to only satisfy my intellectual curiosity.</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