SHARE
TWEET

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

a guest Jan 6th, 2014 46 Never
  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. }
RAW Paste Data
Top