Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Find duplicates within a list in O(n) keeping original order

By: a guest on Jan 6th, 2014  |  syntax: Perl  |  size: 0.80 KB  |  views: 39  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #!/usr/bin/perl -w
  2.  
  3. # Find duplicates.
  4. # Input is a list of numbers separated by space, from STDIN, example: 5 23 7 3 5 89 12 -34 7 355 0 0 12 5
  5. # Output is a list of numbers separated by space, on STDOUT, example: 5 7 12 0
  6.  
  7. use strict;
  8. use warnings;
  9.  
  10. my $input = <STDIN>;
  11. chomp($input);
  12.  
  13. my $list = [ split /\ /, $input ];
  14. my $dups = dups($list);
  15. print join(" ", @{$dups})."\n";
  16.  
  17. sub dups {
  18.     my $list = shift;
  19.  
  20.     my $visited = {};
  21.     my $dups = {};
  22.     my $result = [];
  23.  
  24.     foreach my $item (@{$list}) {
  25.         if(defined $visited->{$item}) { # dup
  26.             if(!defined $dups->{$item}) { # avoid storing dups twice
  27.                 $dups->{$item} = 1;
  28.                 push @{$result}, $item;
  29.             }
  30.         }
  31.         $visited->{$item} = 1;
  32.     }
  33.  
  34.     return $result;
  35. }