finding all recurring elements in an array

[Rocky]

Hello Can any one plz give me an algorithm to find all the elements in an array that are repeated atleast once? Thanks in advance Rocky

[El Corazon]

Rocky71 wrote:

Can any one plz give me an algorithm to find all the elements in an array that are repeated atleast once?

brute force: read all, check for match on all. Now if you want minimal search, now you are talking fun....

_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

[Dan Neely]

Just add a sort pass. With potential duplicates adjacent to each other an O(n) detection routine is trivial.

-- You have to explain to them [VB coders] what you mean by "typed". their first response is likely to be something like, "Of course my code is typed. Do you think i magically project it onto the screen with the power of my mind?" --- John Simmons / outlaw programmer

[El Corazon]

dan neely wrote:

Just add a sort pass.

true, it said nothing about order. There you go, two algorithms, issue solved. :)

_________________________ Asu no koto o ieba, tenjo de nezumi ga warau. Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

[Rocky]

yea i guess there's no other option but to use brute force

[Luc Pattyn]

well, what did you expect ? Here are two approaches without any visible sorting: 1. just enter the numbers one by one in a hashtable; use the numbers as the key, and their multiplicity as the value. So to add a[i], check for presence of key a[i]; if not, add the pair (a[i], 1), else replace (a[i], value) by (a[i], value+1). When done, enumerate the keys with value>=2 2. Since you are not interested in actual multiplicity values, you could try two simple lists: one for "seen just once", the other for "seen more than once". Now for each a[i] first test the "more than once", if not present, the "just once", and move/add the item appropriately. Dont be surprised if this takes longer, for new numbers you are searching two lists (albeit they both are smaller). For both of the above methods, here is a big optimization: just do it for all numbers but the last one. If these all appear more than once, there is no need to read the last number at all. :)

Luc Pattyn

---

try { [Search CP Articles] [Search CP Forums] [Forum Guidelines] [My Articles] } catch { [Google] }

---

[PICguy]

If you want the elements themselves simply sort your list. If you also need the original index values you will have to sort element numbers along with the elements. After sorting the problem becomes trivial.