CODEWITHSUNDEEP
javaarraysduplicates
Snowman
Snowman

Reputation: 32091

Java Array, Finding Duplicates

I have an int array, and am looking for duplicates.

int[] zipcodelist = // ...

duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
    for(k = 0; k < zipcodeList.length; k++){
        if (zipcodeList[k] == zipcodeList[j]){
            duplicates = true;
        }
    }
}

However, this code doesn’t work when there are no duplicates. duplicates still ends up being true. Why’s that?

Upvotes: 71

Views: 294904

Answers (20)

Oleh Tatsiun
Oleh Tatsiun

Reputation: 939

Example:

int[] array = {10, 2, 2, 3, 19, 5, 6, 7, 16, 17, 18, 19};
Set<Integer> duplicates = new HashSet<>();

for (int i = 0; i < array.length - 1; i++) {
    for (int j = i + 1; j < array.length; j++) {
       if (array[i] == array[j]) {
           duplicates.add(array[i]);
       }
    }
}
        
System.out.println(duplicates);

Output: [2, 19]

Upvotes: 0

Gokulprasanth T
Gokulprasanth T

Reputation: 1

    class Solution {
public int findDuplicate(int[] nums) {
    int pre =nums[0], i=0,p=0;
    while(i<nums.length){
        if(nums[pre]!=-1){
            p = nums[pre];
            nums[pre] =-1;  
            pre =p;
        }
        else {
            break;
        }
        i++;
    } 
    return pre;
}

public static void main(String args[]){
  int [] arr = {1,3,4,2,2};
  System.out.println(findDuplicate(arr));
}
}

Upvotes: 0

Vignesh Kumar
Vignesh Kumar

Reputation: 1

public class Rough_work {

    public static void main(String[] args){
        int arr[] = new int[]{1,2,1,3,2,3,1,4,5,4};

        int dup = 0;
         for(int i = 0; i<arr.length;i++){
             for(int j =i+1; j<arr.length;j++){
                 if(arr[i] == arr[j]){
                     System.out.print(arr[i]);
                     break;
                 }
             }
         }

    }
}

Upvotes: 0

Pathiranage Dilshan
Pathiranage Dilshan

Reputation: 1

import java.util.*;
class Example{
    public static boolean duplicate(int[] a) {
        for (int i=0 ; i<a.length-1 ; i++){
            for (int j = i+1; j<a.length ; j++){
                if(a[i]==a[j]){
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String []args) {
        int[] ar={34,65,87,19,94,72,83,47,89};      
        System.out.println(Arrays.toString(ar));//[34,65,87,19,94,72,83,47,89]
        System.out.println("ar is a duplicate array : " + duplicate(ar)); //false
        
        int[] br={34,65,87,19,94,72,83,94,89};      
        System.out.println(Arrays.toString(br));//[34,65,87,19,94,72,83,94,89]
        System.out.println("br is a duplicate array : "+  duplicate(br)); //true
    }
}

Upvotes: 0

ny3an6
ny3an6

Reputation: 1

public static <T> Set<T> getDuplicates(Collection<T> array) {
    Set<T> duplicateItem = new HashSet<>();
    Iterator<T> it = array.iterator();
    while(it.hasNext()) {
        T object = it.next();
        if (Collections.frequency(array, object) > 1) {
            duplicateItem.add(object);
            it.remove();
        }
    }
    return duplicateItem;
}

// Otherway if you dont need to sort your collection, you can use this way.

public static <T> List<T> getDuplicates(Collection<T> array) {
    List<T> duplicateItem = new ArrayList<>();
    Iterator<T> it = array.iterator();
    while(it.hasNext()) {
        T object = it.next();
        if (Collections.frequency(array, object) > 1) {
            if (Collections.frequency(duplicateItem, object) < 1) {
                duplicateItem.add(object);
            }
            it.remove();
        }
    }
    return duplicateItem;
}

Upvotes: 0

meren
meren

Reputation: 442

  public static void findDuplicates(List<Integer> list){
    if(list!=null && !list.isEmpty()){
      Set<Integer> uniques = new HashSet<>();
      Set<Integer> duplicates = new HashSet<>();

      for(int i=0;i<list.size();i++){
        if(!uniques.add(list.get(i))){
          duplicates.add(list.get(i));
        }
      }
      System.out.println("Uniques: "+uniques);
      System.out.println("Duplicates: "+duplicates);
    }else{
      System.out.println("LIST IS INVALID");
    }
  }

Upvotes: 0

Jyoti Nagpal
Jyoti Nagpal

Reputation: 11

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 < 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);
      }

}

}

Upvotes: 0

Ferdinand Tembo
Ferdinand Tembo

Reputation: 11

public static ArrayList<Integer> duplicate(final int[] zipcodelist) {

    HashSet<Integer> hs = new HashSet<>();
    ArrayList<Integer> al = new ArrayList<>();
    for(int element: zipcodelist) {
        if(hs.add(element)==false) {
            al.add(element);
        }   
    }
    return al;
}

Upvotes: 1

Huy Le
Huy Le

Reputation: 667

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.

Upvotes: 15

amk
amk

Reputation: 70

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 < 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));
          }
       }
   }
}

Upvotes: 0

AR Akash
AR Akash

Reputation: 21

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<Integer,Integer> h = new HashMap<Integer,Integer>();


        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<arr.length; i++)
            arr[i]=s.nextInt();
        for(int i=0; i<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>0)
        { 
            for(int i=0;i<l;i++)
                System.out.println(arr1[i]);
        }
        else
            System.out.println(-1);
    }
}

Upvotes: 0

Huy H&#243;m Hỉnh
Huy H&#243;m Hỉnh

Reputation: 617

@andersoj gave a great answer, but I also want add new simple way

    private boolean checkDuplicateBySet(Integer[] zipcodeList) {
        Set<Integer> 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 < zipcodeList.length; i++) {
            zipcodeIntegerArray[i] = Integer.valueOf(zipcodeList[i]);
        }

        Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeIntegerArray));
        if (zipcodeSet.size() == zipcodeList.length) {
            return true;
        }
        return false;
    }

Hope this helps!

Upvotes: 0

Rolando F
Rolando F

Reputation: 196

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.

Upvotes: 2

Sephiroth
Sephiroth

Reputation: 1

How about using this method?

HashSet<Integer> zipcodeSet = new HashSet<Integer>(Arrays.asList(zipcodeList));
duplicates = zipcodeSet.size()!=zipcodeList.length;

Upvotes: 0

andersoj
andersoj

Reputation: 22924

On the nose answer..

duplicates=false;
for (j=0;j<zipcodeList.length;j++)
  for (k=j+1;k<zipcodeList.length;k++)
    if (k!=j && 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<Integer> lump = new HashSet<Integer>();
  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<zipcodelist.length;j++)
      for (int k=j+1;k<zipcodelist.length;k++)
        if (k!=j && 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 < sizes.length; sizei++) {
      System.err.println("Trial for zipcodelist size= "+sizes[sizei]);
      for (int rep = 0; rep < REPS; rep++) {
        int[] zipcodelist = new int[sizes[sizei]];
        for (int i = 0; i < 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 < 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.

Upvotes: 165

Lie Ryan
Lie Ryan

Reputation: 64923

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<zipcodeList.length;j++) {
    for (k=j+1;k<zipcodeList.length;k++) {
        if (zipcodeList[k]==zipcodeList[j]){ // or use .equals()
            return true;
        }
    }
}
return false;

Upvotes: 16

doobop
doobop

Reputation: 4520

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.

Upvotes: 2

codaddict
codaddict

Reputation: 455380

To check for duplicates you need to compare distinct pairs.

Upvotes: 5

KitsuneYMG
KitsuneYMG

Reputation: 12901

Don't use == use .equals.

try this instead (IIRC, ZipCode needs to implement Comparable for this to work.

boolean unique;
Set<ZipCode> s = new TreeSet<ZipCode>();
for( ZipCode zc : zipcodelist )
    unique||=s.add(zc);
duplicates = !unique;

Upvotes: 1

james_bond
james_bond

Reputation: 6906

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

Upvotes: 2

Related Questions