return duplicates from an array in efficient way in java

Question

I want to return duplicates in an array.

int[] strArray = new int[] {1,1, 2, 3, 2, 2, 3};

I have used below method to return duplicates.

private static Set<Integer> checkDuplicate(int[] intArray) {
    Set<Integer> values = new HashSet<>();

    for (int i = 0; i < intArray.length - 1; i++) {
        if (intArray[i] == (intArray[i + 1])) {
            values.add(intArray[i]);
        }

        else
            System.out.println("not equal");
    }

    return values;
}

But in this way it checks only the consequtive values.And this needs huge comparisons and time consuming. So is there any better way to do this?

http://stackoverflow.com/questions/3951547/java-array-finding-duplicates — laitinen, Jun 17 '14 at 07:04

score 3 · Answer 1 · answered Jun 17 '14 at 07:08

3

If you do not want to use hashing (HashSet or HashMap), you can first sort the array. And then, you can find duplicates by checking consecutive values. Overall, this method has O(n log n) time complexity.

answered Jun 17 '14 at 07:08

fajarkoe

1,543
10
12

score 2 · Answer 2 · answered Jun 17 '14 at 07:11

You may try this example:

import java.util.*;
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] strArray = new int[] {1,1, 2, 3, 2, 2, 3, 4, 7, 5, 4};
        Set<Integer> duplicates = checkDuplicate(strArray);
        System.out.printf("Duplicates: %s\n", duplicates);
    }
    private static Set<Integer> checkDuplicate(int[] intArray)
    {
        Set<Integer> duplicates = new HashSet<Integer>();
        Set<Integer> tmp = new HashSet<Integer>();
        for(Integer i: intArray)
        {
            if(!tmp.add(i))
            {
                duplicates.add(i);
            }
        }
        return duplicates;
    }
}

score 1 · Accepted Answer · answered Jun 17 '14 at 07:04

If efficiency is what you are looking for then use HashMap that it has O(1) speed, Also iterate the array of integers in enhanced forloop because it is slightly faster than ordinary forloop

 private static Set<Integer> checkDuplicate(int[] intArray) {
    HashMap<Integer,Integer> values = new HashMap<Integer,Integer>();
    Set<Integer> values2 = new HashSet<Integer>();


    for(Integer i : intArray) //0(n)
    {
        if(values.get(i) != null) //O(1)
            values2.add(i);
        else
            values.put(i, i);
    }


    return values2;
}

TheLostMind · Answer 4 · 2014-06-17T07:16:00.387

0

public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 1, 4, 4, 1, 5 };
        // System.out.println(Arrays.toString(arr));
        List<Integer> l = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            l.add(i, arr[i]);
        }
        // System.out.println(l);
        Set<Integer> set = new HashSet<Integer>();
        for (int j = 0; j < l.size(); j++) {
            if (Collections.frequency(l, l.get(j)) > 1) {
                set.add(l.get(j));
            }
        }

        System.out.println(set);

    }

O/P :
[1, 4]

edited Jun 17 '14 at 07:16

answered Jun 17 '14 at 06:58

TheLostMind

35,966
12
68
104

This will just give count of each duplicate, not the value. – sudmong Jun 17 '14 at 07:04
I want to return the values which has duplicates. Not the frequency of duplicates. – kkk Jun 17 '14 at 07:08
This has O(n^2) time complexity, which the OP is trying to avoid. – fajarkoe Jun 17 '14 at 07:18

score 0 · Answer 5 · edited May 23 '17 at 12:27

0

Scan your input and store each number with it's count in a Map<Interger, Integer>. Then loop over the Map and put all keys with value>1 in the resulting Set

See also here: https://stackoverflow.com/a/15217535/461499

edited May 23 '17 at 12:27

Community

1
1

answered Jun 17 '14 at 07:01

Rob Audenaerde

19,195
10
76
121

score 0 · Answer 6 · answered Jun 17 '14 at 07:08

0

You must have to use Collections.frequency

It uses only equals method. If you use any collection Map,Set,List which uses equals method to compare two objects as well as Has collection uses hashCode methods which takes more processing time.

answered Jun 17 '14 at 07:08

Nitul

997
12
35

return duplicates from an array in efficient way in java

6 Answers6