home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3395 < prev    next >
Encoding:
Internet Message Format  |  1993-01-02  |  1.4 KB
  1. Path: sparky!uunet!pipex!bnr.co.uk!uknet!mcsun!sun4nl!and!jos
  2. From: jos@and.nl (Jos Horsmeier)
  3. Newsgroups: comp.programming
  4. Subject: Re: Locating duplicates
  5. Message-ID: <4279@dozo.and.nl>
  6. Date: 2 Jan 93 11:51:09 GMT
  7. References: <C07FJo.4vq@ux1.cso.uiuc.edu>
  8. Organization: AND Software BV Rotterdam
  9. Lines: 33
  10.  
  11. In article <C07FJo.4vq@ux1.cso.uiuc.edu> ceblair@ux1.cso.uiuc.edu (Charles Blair) writes:
  12. |
  13. |   Given a large array of integers.  Is there a way to identify duplicates
  14. |which is substantially less work than sorting the array?
  15.  
  16. If you're low on memory and the array is really large, there is no better
  17. way than to sort the array and scan the sorted array afterwards, checking
  18. for duplicates. This would cost you O(n*log(n)) time to do the job.
  19.  
  20. On the other hand, if you're not low on memory and if you know the range
  21. of the numbers in the array, say Min and Max, you could use an index
  22. scheme as follows:
  23.  
  24. for all i in Min and Max in index
  25.     index[i] = unset
  26.  
  27. for all i in Minindex and Maxindex in array
  28.     if index[array[i]] != unset then
  29.         duplicate detected
  30.     else
  31.         index[array[i]]= i
  32.  
  33. Here index[j] points to the location in the array where the number j
  34. can be found, if present.  This algorithm (and it's memory usage) is 
  35. all very dependent on the actual numbers Min and Max (the lowest and 
  36. highest values found in the array.) But it'll cost you only O(n) time 
  37. to scan the array.
  38.  
  39. I hope this helps a bit,
  40.  
  41. kind regards and a happy new year,
  42.  
  43. Jos aka jos@and.nl
  44.