Tuesday, February 8, 2011

Count of repeated entities in a List or Array

Reader, 
Writing a useful blog on how to find:
1) Count of repeated integers in a List. 
2) Count of repeated integers in an Array.
3) Missing element in an Array having some integers in a range, numbers are in random order.
4) Count of repeated entities (String, Double, Integer) in an Array.

Consider that I have a list of integers with the individual  values ranging from 0 to 9. The list size is large 
i.e. in thousands and these individual numbers keep repeating. 

I want an approach to determine the number of times an individual value is repeated in the list.
I have written two programs on this, please go as below:
===================================================
import java.util.ArrayList;
import java.util.List;
//commons-collections-3.2.1.jar
import org.apache.commons.collections.bag.HashBag;
public class HashBagCount {
    public static void main(String[] args) {
        List<Integer> values = new ArrayList<Integer>();
        values.add(1);
        values.add(1);
        values.add(1);
        values.add(12);
        values.add(3);
        values.add(12);
        values.add(1);
        values.add(3);
        values.add(12);
        values.add(3);
        values.add(3);

        HashBag bag = new HashBag();
        bag.addAll(values);   //Basically traversing the list

        int count = bag.getCount(1);
        System.out.println("Count 1 : "+count);

        count = bag.getCount(3);
        System.out.println("Count 13 : "+count);

        count = bag.getCount(12);
        System.out.println("Count 12 : "+count);
    }
}

//Output:
Count 1 : 4
Count 13 : 4
Count 12 : 3
===================================================
//Inside an Array, using Exclusive OR operator
import java.util.HashMap;
public class RepeatedElements {
    public static void main(String[] args) {
        int arr[]=new int[]{1,1,2,2,3,4,5,6,7,8,4,5,78,67,56,90,67,67};
        int count=0;
        HashMap map=new HashMap();

        for(int i=1;i<arr.length;i++){
            count=1;
            for(int j=0;j<i;j++){
                if((arr[i]^arr[j])==0) {
                    count++;
                    map.put(arr[i],count);
                    //System.out.println(arr[i]);
                }
            }    
        }
        System.out.println(map);
    }
}
//Output:
{2=2, 4=2, 67=3, 1=2, 5=2}
===================================================
public class FindMissingNumber {
    public static void main(String[] args) {
        int n=20;  //This is the size of array whose missing number to be found.
        //For below array it is 20.

        //Only 19 elements are available in below array.
        int arr[]=new int[]{1,2,4,3,7,6,5,8,9,10,0,12,15,14,13,18,16,17,19,20}; 
        int sumCurrArray=0;
        System.out.print("Array Elements: ");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
            if(arr[i]==0)
                ;
            else
                sumCurrArray=sumCurrArray+arr[i];
        }
        System.out.println();

        int sum=(n*(n+1))/2;
        System.out.println("Sum of "+n+" elements: "+sum);
        System.out.println("Missing number: "+(sum-sumCurrArray));
    }
}
//Output:
Array Elements: 1 2 4 3 7 6 5 8 9 10 0 12 15 14 13 18 16 17 19 20 
Sum of 20 elements: 210
Missing number: 11
===================================================
Reader, Giving one more example below which works for all primitive data types. In fact it works for String 
array too. But just to remind: JVM maintains a Memory Pool for String variables. I mean to say, see the smaller
example below:
-----------------------------------
public class StringExample {
    public static void main(String[] args) {
        String s="a";
        String s1="a";
        String s2=new String("a");
        System.out.println(s==s1);   //Maintains a pool
        System.out.println(s==s2);   //No pool here.
        
    }
}
//Output
true
false
-----------------------------------
And hence the below example works fine for String array too but array should have Strings put 
into DOUBLE QUOTE like "deepak" and "deepak", not like "deepak" and new String("deepak"), please see below 
example:

public class RepeatedElementsDouble {
    public static void main(String[] args) {
        //double array[]=new double []{2,3,4,5,5.1,4.0,90,4.0,5.0,5.1,3.002,3.0};
        String array[]=new String []{"2","deepak","rajesh","deepak","5.1","2","90","90"};   //This is OK as per this Example.
        //String array[]=new String []{"2","deepak","rajesh",new String("deepak"),"5.1","2","90","90"}; //This is not OK.
        //int[] array = {1, 3, 5, 6, 2, 3, 6, 4, 3, 2, 1, 6, 3, 3, 6, 4, 8, 9, 0};

        boolean[] check = new boolean[array.length];  //By default all are false

        for(int i = 0; i < array.length; i++) {
            if(check[i])
                continue;
            int count = 0;

            for(int j = i; j < array.length; j++) {
                if(check[j])
                    continue;
            
                if(array[j] == array[i]) {
                    check[j] = true;
                    count++;
                }
            }
            System.out.println("\""+array[i] + "\" is present: " + count + " time.");
        }
    }
}
//Output:
"2" is present: 2 time.
"deepak" is present: 2 time.
"rajesh" is present: 1 time.
"5.1" is present: 1 time.
"90" is present: 2 time.

========================END===========================

No comments:

Post a Comment