-2

I'm trying to count how many duplicate items are in an array.

Example:

[0, 2, 0] would return 2, [0, 0, 0] would return 3, [0, 1, 2] = 0

So far I have it working for when all three items are equal, but I'm not sure why it's returning one less than what it should for 2 items being the same.

    int equal = 0;

    for(int i = 0; i < recent.length; i++) {
        for(int j = i; j < recent.length; j++) {
            if(i != j && recent[i].equals(recent[j])) {
                equal++;
            }
        }
    }
4
  • You need to rethink the problem.
    – asheeshr
    Dec 1, 2012 at 9:25
  • In particular, you should rethink your definition of the problem. What exactly are you trying to count - how many duplicated elements there are, or how many pairs of equal elements there are?
    – Jon Skeet
    Dec 1, 2012 at 9:26
  • Invest some time in reading the docs for HashMap.
    – Will A
    Dec 1, 2012 at 9:27
  • What would [0, 2, 0, 2, 0] return - just a single number? What would it be?
    – xagyg
    Dec 1, 2012 at 12:04

8 Answers 8

1

Your algorithm is flawed in the following way: for every element in the array you look at all the elements after that element and if they happen to be equal, you increase the counter. However when you have 3 same elements, you count the last one twice - when you run internal loop for first and for second element. Moreover you never count the first element.

So it works by accident for [0, 0, 0] but doesn't work for other inputs.

1

I think that having nested loops is quite inefficient. You should be able to do it in o(n) rather than o(n^2).

If you time yours against the following...

public void run() {
    int[] array = createRandomArray(2000000, 1000000);
    System.out.println(countNumDups1(array));
}


private int[] createRandomArray(int numElements, int maxNumExclusive) {
    int[] array = new int[numElements];
    Random random = new Random();
    for (int i = 0; i < array.length; i++) {
        array[i] = random.nextInt(maxNumExclusive);
    }
    return array;
}

private int countNumDups1(int[] array) {
    Map<Integer, Integer> numToCountMap = new HashMap<>();
    for (int i = 0; i < array.length; i++) {
        Integer key = array[i];
        if (numToCountMap.containsKey(key)) {
            numToCountMap.put(key, numToCountMap.get(key) + 1);
        }
        else {
            numToCountMap.put(key, 1);
        }
    }
    int numDups = 0;
    for (int i = 0; i < array.length; i++) {
        Integer key = array[i];
        if (numToCountMap.get(key) > 1) {
            numDups++;
        }
    }
    return numDups;
}

I think you'll find the above is much faster even considering the horrible inefficiency of autoboxing and object creation.

1
  • mfb's solution is better than mine. Both are o(n) but his will run a few times faster I imagine.
    – kelceyp
    Dec 1, 2012 at 10:19
1

The code you gave counts equivalences, so it adds one every time an element equals another element.

It sounds like what you want is the number of duplicate items, which is the same as (length - number of items that don't have a duplicate). I will call the latter "uniqueItems".

I would recommend the following:

// set of every item seen
Set<Integer> allItems = new HashSet<Integer>();
// set of items that don't have a duplicate
Set<Integer> uniqueItems = new HashSet<Integer>();

for(int i = 0; i < recent.length; i++) {
    Integer val = i;
    if(allItems.contains(val)) {
        // if we've seen the value before, it is not a "uniqueItem"
        uniqueItems.remove(val); 
    } else {
        // assume the value is a "uniqueItem" until we see it again
        uniqueItems.add(val);
    }
    allItems.add(val);
}
return recent.length - uniqueItems.size();
1

The below code works perfectly to find the duplicates

    int array[] = {1,2,3,4,5,2,3,4,5,3,4,5,4,5,5};

    HashMap<Integer,Integer> duplicates = new HashMap<Integer,Integer>();
    for(int i=0; i<array.length; i++)
    {
        if(duplicates.containsKey(array[i]))
        {
            int numberOfOccurances = duplicates.get(array[i]);
            duplicates.put(array[i], (numberOfOccurances + 1));
        }else{
            duplicates.put(array[i], 1);
        }
    }
    Iterator<Integer> keys = duplicates.keySet().iterator();
    System.out.print("Duplicates : " );
    while(keys.hasNext())
    {
        int k = keys.next(); 
        if(duplicates.get(k) > 1)
        {
            System.out.print(" "+k);
        }
    }
0

You are counting the number of pairs of indices that have equal values. What you claim to want is the total size of all sets of equal elements that have more than one element in them.

I would use a Map or similar to count the total number of appearances of a given value. At the end, iterate over the key values adding the number of appearances for each key that has more than one appearance.

0
int intArray[] = {5, 1, 2, 3, 4, 5, 3, 2};  

String val = "";

int c = 1;

Map<Integer, Integer> nwmap = new HashMap<Integer, Integer>();  

for (int i = 0; i < intArray.length; i++) {

    Integer key = intArray[i];

        if(nwmap.get(key) != null && nwmap.containsKey(key)){

        val += " Duplicate: " +String.valueOf(key)+"\n";

    }else{

        nwmap.put(key, c);

            c++;

    }

}

LOG.debug("duplicate value:::"+val);
0
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;


public class ArrayDuplicateCount {

    /**
     * @author:raviteja katari
     */
    public static void main(String[] args) {
        int intArray[] = {5, 1,4,4,4,5,1,2,1,2,5,5};  


        //for counting duplicate items
        int c = 0;

        //creating map collection to hold integers as keys and Cont as value
        Map<Integer, Integer> nwmap = new LinkedHashMap<Integer, Integer>();  

        for (int i = 0; i <intArray.length; i++) {

            //Assigning array element to key 
            Integer key = intArray[i];

                //this code checks for elemnt if present updates count value else 
                //put the new Array elemnt into map and increment count

                if(nwmap.containsKey(key)){

                    //updating key value by 1 
                    nwmap.put(key, nwmap.get(key) + 1);

            }else{

                //Adding new array element to map and increasing count by 1
                  nwmap.put(key, c+1);


                   }

                           }
          //printing map
        System.out.println(nwmap);
    }

}

output: {5=4, 1=3, 4=3, 2=2}

0
    public void TotalduplicateNumbers {
    int a[] = {2,8,2,4,4,6,7,6,8,4,5};
    Map<Integer,Integer> m = new HashMap<Integer,Integer>();
    for(int i=0;i<a.length;i++){            

            if(!m.containsKey(a[i]))
            {
                m.put(a[i], 1);
            }
            else
            {
                m.put(a[i], (m.get(a[i])+1));
            }

    }

    for(Integer i:m.keySet()){
        System.out.println("Number "+i+" "+"Occours "+m.get(i)+" time,");
    }
}

We have an array containing 11 numbers, The logic is to create a map using these no. in which KEYS of map would be the actual number that must be entered by user and no. of occournce of that actual no. would be the value of that KEY. Here, containsKey() method checks whether the map contain that key already and return boolean value true or false as applied.If it does not contain then add that key into the map and its corresponding value should be 1 otherwise key would have already be contained in map so get the value of that key using get() and increment it by 1. Finally printing the map.

OUTPUT:--

Number 2 Occours 2 time, Number 4 Occours 3 time, Number 5 Occours 1 time, Number 6 Occours 2 time, Number 7 Occours 1 time, Number 8 Occours 2 time,

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.