home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3415 < prev    next >
Encoding:
Text File  |  1993-01-05  |  1.1 KB  |  25 lines
  1. Newsgroups: comp.programming
  2. Path: sparky!uunet!usc!howland.reston.ans.net!wupost!uwm.edu!linac!att!att!dptg!ulysses!ulysses.att.com!kpv
  3. From: kpv@ulysses.att.com (Phong Vo)
  4. Subject: Re: Locating duplicates
  5. Message-ID: <1993Jan5.150010.27104@ulysses.att.com>
  6. Date: Tue, 5 Jan 1993 15:00:10 GMT
  7. References: <C07FJo.4vq@ux1.cso.uiuc.edu> <1993Jan2.041658.21596@organpipe.uug.arizona.edu>
  8. Organization: AT&T Bell Labs
  9. Lines: 14
  10.  
  11. In article <1993Jan2.041658.21596@organpipe.uug.arizona.edu> dave@cs.arizona.edu (Dave Schaumann) writes:
  12. >In article <C07FJo.4vq@ux1.cso.uiuc.edu>, ceblair@ux1 (Charles Blair) writes:
  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. >...lots of good suggestions for the general case...
  17.  
  18. But most often this kind of question comes up in practice
  19. because you have a large array of integers in a small range.
  20. In that case, using a bit map for the range, you can do it
  21. in linear time and space proportion to the range size.
  22.   
  23. Phong Vo, kpv@ulysses.att.com
  24. AT&T Bell Labs, 600 Mountain Ave, Murray Hill, NJ07974
  25.