counting duplicates numbers in array

[SiliconWizard]

I am trying to write code that can count duplicate numbers in array for following sequences

1 2 1 2 5   2 found 1 times
1 2 2 2 5   2 found 2 times
1 2 3 4 5    not found
9 9 9 9 9   9 found 4 times

I have read the original post many times and can't see what defines a duplicate.  Take for example the first and second entries.  Why doesn't the second case have "3 times" instead of 2 times.  If one numbers the places L-->R  a,b,c,d,e

case 1 found 2 duplicated 1 time (ie.., b & d), even though they are separated by a non-2.  Of course, 1 is also duplicated, but ignore that for the time being.

case 2 found 2 duplicated 2 times, which I presume are positions b&c + c&d.  Why isn't b&d also a duplicate?  In other words, in case 2, the middle 2 is counted as part of 2 duplicates.  Why can't the leading and terminating 2 's be considered part of duplicates?

case  3 counts the three middle 9's as part of duplicates twice, but not the leading and trailing ones.

In other words, what is the rule (s) for a duplicate.

EDIT: I am fine if the definition is occurances -1.
EDIT2: @mariush  I didn't see your comment before my first edit.  I was thinking in terms of pairs.

Quite right, the OP's question was really ill-defined. Many of us have just taken it as counting *all* duplicates in some array, but the way it was formulated, it's absolutely as clear as mud.

If you can't ask the right question, finding the answer is a random process.

[ejeffrey]

If your list does not meet the criteria for a counting sort to be efficient, then sorting first will be much slower than simply counting the duplicates.

The only “simply counting the duplicates when a counting sort is not efficient” algorithm I can readily come up is O(N^2) in time, while O(N * log N) is typical for an efficient general sort. Am I missing an efficient “simply count duplicates” algorithm?

You can use a hash table to store the counts.  Since hash table accesses are nominally O(1), that should have an average time O(N), but the worst case behavior is O(N^2) for a basic hash table.  However, its usually not desirable to worry about asymptotic log(N) terms -- since for practical systems log(N) is always limited to a pretty small number the constant factor is often as important as the difference between O(N) and O(N lg N). When you are worrying about that it often makes sense to count operations exactly rather than take an asymptotic limit.

[sokoloff]

Hash table is a great answer that I missed. Thanks!

[DiTBho]

Good, just ... hash tabs usually have collisions probability.
Need to be carefully setup to avoid/minimize.

Hash can use ROTR and ROTL 

[Nominal Animal]

Good, just ... hash tabs usually have collisions probability.

Like I said in #16, optimum size is about twice the input array size.  This assumes you use the common scheme of probing [H%N] and if it is occupied but non-matching, [(H+D)%N], [(H+2*D)%N], [(H+3*D)%N], and so on, until either an unused slot or the matching value is found.  (H being the hash of the value, N the hash table size, and D the probe step size, often 1.)
Obviously, to avoid the costly modulo operation per probe, one should make N a power of two about twice as large as the array size.

Really, a generic function to count the number of occurrences in an array, needs all three: nested-loop O(N²), range histogram, and a hash table.
If the array is short, the nested loop one makes most sense, because the iterations are fast, and the total number of iterations for small N, say up to a dozen perhaps, is faster to do than the alternatives.  Otherwise, do a pass over the array entries, and find out the continuous range of values.  If it is smaller than say 4× the number of entries in the array, you allocate an array of counters large enough for each possible value, and do the range histogram.  Otherwise, you allocate a hash table of about 2× the number of entries in the array (noting that each hash table entry contains both the original value, and the count), and do the hash table approach.

Is it worth it?  I dunno.  I don't think so.  But knowing the three approaches is useful, because ones use cases tend to fall into one of the three.

It's like with radix-sorting IEEE 754 double-precision numbers.  It is quite straightforward: you just need to XOR-mask the high bit if unset, and all bits if set, so that when interpreted as an unsigned 64-bit integer, the values sort exactly like their original finite double-precision values would.  Redo afterwards to return the original values.  The optimal pass sizes do depend on the cache architecture, and although it does scale as O(N), you need bloody huge arrays, tens of millions to billions of doubles, before you beat the traditional O(N log N) sort algorithms.  In many cases, by doing the XOR-mask pass before and after, and treating the doubles as 64-bit integers, you can speed up the sort enough that the amount of data at which the difference would matter to a human, is too large to worry about: the code maintenance cost is more important in practice.

[ejeffrey]

Good, just ... hash tabs usually have collisions probability.
Need to be carefully setup to avoid/minimize.

Sure.  Keeping hash tables efficient under different working conditions is one of the most well studied problems in computing.  It's certainly possible to screw up, but usually possible to do correctly.