home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / programm / 3413 < prev    next >
Encoding:
Text File  |  1993-01-05  |  1.7 KB  |  51 lines
  1. Path: sparky!uunet!spool.mu.edu!agate!mickey!bsmith
  2. From: bsmith@mickey.NoSubdomain.NoDomain (Brian Smith)
  3. Newsgroups: comp.programming
  4. Subject: Re: Locating duplicates
  5. Date: 5 Jan 1993 07:12:55 GMT
  6. Organization: University of California, Berkeley
  7. Lines: 37
  8. Sender: bsmith@mickey (Brian Smith)
  9. Distribution: world
  10. Message-ID: <1ibcdnINNpb1@agate.berkeley.edu>
  11. References: <1993Jan2.041658.21596@organpipe.uug.arizona.edu> <DOUGM.93Jan2014723@titan.cs.rice.edu> <C07z6L.1Aq@world.std.com> <1993Jan5.043456.29130@micor.ocunix.on.ca>
  12. NNTP-Posting-Host: mickey.cs.berkeley.edu
  13.  
  14. In article <1993Jan5.043456.29130@micor.ocunix.on.ca>, goss@micor.ocunix.on.ca (Timothy D. Goss) writes:
  15. |> You can locate ALL duplicates in a list of integers with a single pass of the
  16. |> list which is O(n) in time but it will require an array with 64K elements.  The
  17. |> program below should explain...
  18. |> 
  19. |> typedef unsigned char byte;
  20. |> 
  21. |> static byte found[65536];
  22. |> int intlist[NUM];        
  23. |> 
  24. |> void main(void) 
  25. |> {
  26. |> 
  27. |>    int i;
  28. |>    int check;
  29. |> 
  30. |>    /* assume intlist is filled with NUM integers */
  31. |> 
  32. |>    for (i=0; i<NUM; i++) {
  33. |>       check = intlist[i];
  34. |>       if (found[check] > 0 && found[check] != 0xff) {
  35. |>          printf("%d\n", check);
  36. |>          found[check] = 0xff; /* don't report same dupe twice */
  37. |>       } else {
  38. |>          found[check] += 1; /* first time we saw this one */
  39. |>       }
  40. |>    }
  41. |> 
  42. |> }
  43.  
  44. Uh, maybe I'm really missing something, but won't this crash and burn and
  45. core-dump if the integers are > 16 bits?  Don't try this on an alpha...
  46.  
  47. -------
  48. Brian C. Smith                arpa:  bsmith@cs.Berkeley.EDU
  49. University of California, Berkeley    uucp: uunet!ucbvax!postgres!bsmith
  50. Computer Sciences Department        phone: (510)642-9585
  51.