home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3441 < prev    next >
Encoding:
Internet Message Format  |  1993-01-11  |  1.0 KB
  1. Path: sparky!uunet!pipex!Q.icl.co.uk!dsbc!jura!pete
  2. From: pete@sst.icl.co.uk (Pete Bevin)
  3. Newsgroups: comp.programming
  4. Subject: Re: Locating duplicates
  5. Message-ID: <pete.165741.07Jan93@sst.icl.co.uk>
  6. Date: 7 Jan 93 17:07:04 GMT
  7. References: <C07FJo.4vq@ux1.cso.uiuc.edu> <PERM.93Jan5210346@groucho.csd.uu.se>
  8. Sender: news@dsbc.icl.co.uk
  9. Reply-To: pete@sst.icl.co.uk (Pete Bevin)
  10. Lines: 14
  11. Nntp-Posting-Host: sst.icl.co.uk
  12. Originator: pete@jura
  13.  
  14. Per Mildner writes:
  15. > A general solution to this problem (ie not dependent on the values
  16. > being integers) can be found in an fairly recent CACM article (I don't
  17. > have it handy, probably first half of 1992, you probably could use
  18. > WAIS to find it... ).
  19.  
  20. The article is in CACM, March 1991, pp 62--73.
  21.  
  22. The algorithm given moves duplicated elements to the end of the list,
  23. but it may not preserve the order of the non-duplicate elements.
  24. However, it can preserve them if it is allowed O(n) space.  The authors
  25. did not find a linear-time, constant space, stable algorithm.
  26.  
  27. Pete.
  28.