[Tutor] Testing if a number occurs more than once

[Yigal Duppen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> I think I may be missing out on something really obvious here (such as
> a built-in), but I'm trying to ascertain whether a given number occurs
> more than once in a list. 
...
> (this is the dominant loop of the program). 

Others already suggested the trick of copying, sorting and checking the 
adjacent elements.

However, if this is indeed the dominant loop of the program, it might be even 
better to change the datastructure you use; if your structure guarantees 
order (such as an ordered list), you get rid of the copying and sorting, 
requiring only one loop to check for duplicates. Unless of course you need 
the original order of your input later on.

Another approach might be to construct the frequency table you suggested 
directly from the input. Of course, the applicability of this depends on your 
other uses too.

Complexity of the first approach:
* adding n elements (O(n))
* sorting (O(n log n))
* searching for duplicates (O(n))

Complexity of the second approach:
* adding n elements (O(n log n))  (assuming a sensible implementation of the 
sorted collection)
* searching for duplicates (O(n))

Complexity of the third approach:
* adding n elements (O(n))
* searching for duplicates (O(n))

Hmmm. Now that I look at it, approaches one and to have basically the same 
complexity; so that would mean profiling both approaches for your specific 
problem.

I don't feel coherent. I'd better get some sleep... G'night

YDD
- -- 
http://www.xs4all.nl/~yduppen
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.0 (GNU/Linux)

iD8DBQE96/ZpLsKMuCf5EdwRAuL+AJ42SkXWb0l8AZkLR5FNFeti97ZJ8gCZAdg3
dwX700Z79NSnyuGjzanr87Q=
=07Tj
-----END PGP SIGNATURE-----