Java Array Finding Duplicates

Question

I have an array  and am looking for duplicates   duplicates   false  for j   0  j  lt  zipcodeList length  j         for k   0  k  lt  zipcodeList length  k             if  zipcodeList k     zipcodeList j                duplicates   true                      However  this code doesnt work when there are no duplicates  Whys that

User · Accepted Answer

On the nose answer    duplicates false  for  j 0 j lt zipcodeList length j      for  k j 1 k lt zipcodeList length k        if  k  j  amp  amp  zipcodeList k     zipcodeList j         duplicates true    Edited to switch  equals   back to    since I read somewhere you re using int  which wasn t clear in the initial question   Also to set k j 1  to halve execution time  but it s still O n2    A faster  in the limit  way  Here s a hash based approach   You gotta pay for the autoboxing  but it s O n  instead of O n2    An enterprising soul would go find a primitive int-based hash set  Apache or Google Collections has such a thing  methinks    boolean duplicates final int   zipcodelist      Set lt Integer gt  lump   new HashSet lt Integer gt       for  int i   zipcodelist          if  lump contains i   return true      lump add i         return false      Bow to HuyLe  See HuyLe s answer for a more or less O n  solution  which I think needs a couple of add l steps   static boolean duplicates final int   zipcodelist       final int MAXZIP   99999     boolean   bitmap   new boolean MAXZIP 1      java util Arrays fill bitmap  false      for  int item   zipcodeList       if   bitmap item   bitmap item    true       else return true          return false      Or Just to be Compact  static boolean duplicates final int   zipcodelist       final int MAXZIP   99999     boolean   bitmap   new boolean MAXZIP 1       Java guarantees init to false    for  int item   zipcodeList       if    bitmap item     true   return true     return false      Does it Matter   Well  so I ran a little benchmark  which is iffy all over the place  but here s the code   import java util BitSet   class Yuk     static boolean duplicatesZero final int   zipcodelist          boolean duplicates false      for  int j 0 j lt zipcodelist length j          for  int k j 1 k lt zipcodelist length k            if  k  j  amp  amp  zipcodelist k     zipcodelist j             duplicates true       return duplicates          static boolean duplicatesOne final int   zipcodelist          final int MAXZIP   99999      boolean   bitmap   new boolean MAXZIP   1       java util Arrays fill bitmap  false       for  int item   zipcodelist          if    bitmap item     true           return true            return false         static boolean duplicatesTwo final int   zipcodelist          final int MAXZIP   99999       BitSet b   new BitSet MAXZIP   1       b set 0  MAXZIP  false       for  int item   zipcodelist          if   b get item             b set item  true           else         return true            return false         enum ApproachT   NSQUARED  HASHSET  BITSET                param args         public static void main String   args          ApproachT approach   ApproachT BITSET       final int REPS   100      final int MAXZIP   99999       int   sizes   new int     10  1000  10000  100000  1000000        long     times   new long sizes length  REPS        boolean tossme   false       for  int sizei   0  sizei  lt  sizes length  sizei            System err println  Trial for zipcodelist size    sizes sizei          for  int rep   0  rep  lt  REPS  rep              int   zipcodelist   new int sizes sizei            for  int i   0  i  lt  zipcodelist length  i                zipcodelist i     int   Math random      MAXZIP   1                      long begin   System currentTimeMillis            switch  approach            case NSQUARED             tossme     duplicatesZero zipcodelist              break          case HASHSET             tossme     duplicatesOne zipcodelist              break          case BITSET             tossme     duplicatesTwo zipcodelist              break                     long end   System currentTimeMillis            times sizei  rep    end - begin                  long avg   0        for  int rep   0  rep  lt  REPS  rep              avg    times sizei  rep                 System err println  Size     sizes sizei       avg time                   avg    double REPS    ms                   With NSQUARED   Trial for size  10 Size 10  avg time   0 0ms Trial for size  1000 Size 1000  avg time   0 0ms Trial for size  10000 Size 10000  avg time   100 0ms Trial for size  100000 Size 100000  avg time   9923 3ms   With HashSet  Trial for zipcodelist size  10 Size 10  avg time   0 16ms Trial for zipcodelist size  1000 Size 1000  avg time   0 15ms Trial for zipcodelist size  10000 Size 10000  avg time   0 0ms Trial for zipcodelist size  100000 Size 100000  avg time   0 16ms Trial for zipcodelist size  1000000 Size 1000000  avg time   0 0ms   With BitSet  Trial for zipcodelist size  10 Size 10  avg time   0 0ms Trial for zipcodelist size  1000 Size 1000  avg time   0 0ms Trial for zipcodelist size  10000 Size 10000  avg time   0 0ms Trial for zipcodelist size  100000 Size 100000  avg time   0 0ms Trial for zipcodelist size  1000000 Size 1000000  avg time   0 0ms   BITSET Wins   But only by a hair      15ms is within the error for currentTimeMillis    and there are some gaping holes in my benchmark   Note that for any list longer than 100000  you can simply return true because there will be a duplicate   In fact  if the list is anything like random  you can return true WHP for a much shorter list   What s the moral   In the limit  the most efficient implementation is    return true    And you won t be wrong very often

User · Answer

import java util Scanner   public class Duplicates       public static void main String   args            Scanner console   new Scanner System in           int number   console nextInt            String numb        number          int leng   numb length  -1           if  numb charAt 0     numb charAt 1                 System out print numb substring 0 1                       for  int i   0  i  lt  leng  i                if  numb charAt i   numb charAt i 1                  System out print numb substring i i 1                          else                 System out print numb substring i 1 i 2

User · Answer

To check for duplicates you need to compare distinct pairs

User · Answer

Let s see how your algorithm works   an array of unique values    1  2  3   check 1    1  yes  there is duplicate  assigning duplicate to true  check 1    2  no  doing nothing  check 1    3  no  doing nothing  check 2    1  no  doing nothing  check 2    2  yes  there is duplicate  assigning duplicate to true  check 2    3  no  doing nothing  check 3    1  no  doing nothing  check 3    2  no  doing nothing  check 3    3  yes  there is duplicate  assigning duplicate to true    a better algorithm   for  j 0 j lt zipcodeList length j          for  k j 1 k lt zipcodeList length k              if  zipcodeList k   zipcodeList j       or use  equals               return true                    return false

User · Answer

andersoj gave a great answer  but I also want add new simple way      private boolean checkDuplicateBySet Integer   zipcodeList            Set lt Integer gt  zipcodeSet   new HashSet Arrays asList zipcodeList            if  zipcodeSet size      zipcodeList length                return true                    return false          In case zipcodeList is int    you need convert int   to Integer   first It not auto-boxing   code here  Complete code will be       private boolean checkDuplicateBySet2 int   zipcodeList            Integer   zipcodeIntegerArray   new Integer zipcodeList length           for  int i   0  i  lt  zipcodeList length  i                  zipcodeIntegerArray i    Integer valueOf zipcodeList i                       Set lt Integer gt  zipcodeSet   new HashSet Arrays asList zipcodeIntegerArray            if  zipcodeSet size      zipcodeList length                return true                    return false          Hope this helps

User · Answer

Cause you are comparing the first element of the array against itself so It finds that there are duplicates even where there aren t

User · Answer

public static ArrayList lt Integer gt  duplicate final int   zipcodelist         HashSet lt Integer gt  hs   new HashSet lt  gt         ArrayList lt Integer gt  al   new ArrayList lt  gt         for int element  zipcodelist            if hs add element   false                al add element                          return al

User · Answer

You can use bitmap for better performance with large array       java util Arrays fill bitmap  false        for  int item   zipcodeList          if   bitmap item   bitmap item    true          else break    UPDATE  This is a very negligent answer of mine back in the day  keeping it here just for reference  You should refer to andersoj s excellent answer

User · Answer

You can also work with Set  which doesn t allow duplicates in Java        for  String name   names                       if  set add name     false                 your duplicate element           using add   method and check return value  If add   returns false it means that element is not allowed in the Set and that is your duplicate

User · Answer

Initialize k   j 1   You won t compare elements to themselves and you ll also not duplicate comparisons   For example  j   0  k   1 and k   0  j   1 compare the same set of elements   This would remove the k   0  j   1 comparison

User · Answer

Print all the duplicate elements  Output -1 when no repeating elements are found   import java util     public class PrintDuplicate        public static void main String args             HashMap lt Integer Integer gt  h   new HashMap lt Integer Integer gt               Scanner s new Scanner System in           int ii s nextInt            int k s nextInt            int   arr new  int k           int   arr1 new  int k           int l 0          for int i 0  i lt arr length  i                arr i  s nextInt            for int i 0  i lt arr length  i                 if h containsKey arr i                     h put arr i   h get arr i     1                   arr1 l    arr i                 else                   h put arr i   1                                   if l gt 0                         for int i 0 i lt l i                    System out println arr1 i                      else             System out println -1

User · Answer

How about using this method   HashSet lt Integer gt  zipcodeSet   new HashSet lt Integer gt  Arrays asList zipcodeList    duplicates   zipcodeSet size    zipcodeList length

User · Answer

Don t use    use  equals   try this instead  IIRC  ZipCode needs to implement Comparable for this to work   boolean unique  Set lt ZipCode gt  s   new TreeSet lt ZipCode gt     for  ZipCode zc   zipcodelist       unique   s add zc   duplicates    unique

User · Answer

This program will print all duplicates value from array   public static void main String   args        int   array   new int     -1  3  4  4 4 3  9 -1  5 5 5  5             Arrays sort array     boolean isMatched   false   int lstMatch  -1        for int i   0  i  lt  array length  i                  try                   if array i     array i 1                          isMatched   true                      lstMatch   array i 1                                      else if isMatched                        System out println lstMatch                       isMatched   false                      lstMatch   -1                               catch Exception ex                    TODO NA                            if isMatched              System out println lstMatch

[java] Java Array, Finding Duplicates

On the nose answer..

A faster (in the limit) way

Bow to HuyLe

Or Just to be Compact

Does it Matter?

BITSET Wins!

Examples related to java

Examples related to arrays