Databases
StackOverflow2013
Postsdbo
POFind all duplicates and missing values in a sorted array
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFind all duplicates and missing values in a sorted array
    text
    copied!<p>Suppose you have a sorted range (x to y) of values in an array.</p> <pre><code>x = 3; y = 11; array == 3, 4, 5, 6, 7, 8, 9, 10, 11 </code></pre> <p>But it is possible that some values are duplicated and some are missing, so you might have:</p> <pre><code>array == 4, 5, 5, 5, 7, 8, 9, 10, 10 </code></pre> <p>What's the best way in your language to find all duplicates and missing values so you get:</p> <pre><code>resultMissingValuesArray == 3, 6, 11 resultDuplicatesArray == 5, 5, 10 </code></pre> <p>Here's some C++ code to get you started:</p> <pre><code>#include &lt;vector&gt; #include &lt;iostream&gt; #include &lt;algorithm&gt; using namespace std; const int kLastNumber = 50000; // last number expected in array const int kFirstNumber = 3; // first number expected in array int main() { vector&lt;int&gt; myVector; // fill up vector, skip values at the beginning and end to check edge cases for(int x = kFirstNumber + 5; x &lt; kLastNumber - 5; x++) { if(x % 12 != 0 &amp;&amp; x % 13 != 0 &amp;&amp; x % 17 != 0) myVector.push_back(x); // skip some values else if(x % 9 == 0) { myVector.push_back(x); // add duplicates myVector.push_back(x); } else if(x % 16 == 0) { myVector.push_back(x); // add multiple duplicates myVector.push_back(x); myVector.push_back(x); myVector.push_back(x); } } // put the results in here vector&lt;int&gt; missingValues; vector&lt;int&gt; duplicates; // YOUR CODE GOES HERE // validate missingValues for false positives for(int x = 0; x &lt; (int) missingValues.size(); ++x) { if(binary_search(myVector.begin(), myVector.end(), missingValues.at(x))) cout &lt;&lt; "Oh noes! You missed an unmissed value. Something went horribly, horribly wrong."; } // validate duplicates (I think... errr) vector&lt;int&gt;::iterator vecItr = myVector.begin(); vector&lt;int&gt;::iterator dupItr = duplicates.begin(); while(dupItr &lt; duplicates.end()) { vecItr = adjacent_find(vecItr, myVector.end()); if(*vecItr != *dupItr) cout &lt;&lt; "Oh noes! Something went horribly, horribly wrong."; // oh god while(++dupItr != duplicates.end() &amp;&amp; *(--dupItr) == *(++dupItr) &amp;&amp; *vecItr == *(++vecItr)); ++vecItr; } return 0; } </code></pre> <p>I didn't test the validation parts much, so there may be be something wrong with them (especially with the duplicates one). </p> <p>I will post my own solution as an answer.</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