how to count and return the object that occurs the most in an ArrayList

[Anis Yusof]

Hello everyone.

I have a problem. I would like to know, how to count for duplicate object, and return the highest occurence of object in an ArrayList. For this instance, I am using ArrayList <Integer>; I believed it is also possible for me to use int []. Anyway, these are the sample codes.

    
ArrayList <Integer> id = new ArrayList <Integer> ();

id.add(new Integer(1));
id.add(new Integer(2));
id.add(new Integer(1));
id.add(new Integer(1));
id.add(new Integer(2));
...
id.add(new Integer(n));

In the above codes, there are three 1s, two 2s, and probably other integer that is randomly added. Hence, i want it to return me the Integer 1 object; since Integer 1 occurs the most in this ArrayList.

I have googled it, and searched this forum. But unfortunately, I didn't find what I want. Please help. Thanks!

[Prabhakar Reddy Bokka]

I hope you want to search for the objects containing same value, not the same object.
You are adding a new object every time.

For your problem you need to traverse the entire list and search for the most occurences of the value.
Other option is you can use the search algorithms.

Searching Algorithms

[Gupta Tarun]

If Performance is not a concern the following code should work..

    

ArrayList<Integer> id = new ArrayList<Integer>();

		id.add(new Integer(1));
		id.add(new Integer(2));
		id.add(new Integer(2));
		id.add(new Integer(2));
		id.add(new Integer(1));
		id.add(new Integer(1));
		id.add(new Integer(2));
		id.add(new Integer(3));
		id.add(new Integer(3));
		id.add(new Integer(3));
		id.add(new Integer(3));
		id.add(new Integer(3));

		//Creating a Frequency Map.
		Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

		//defining a set of map entry that sorts based on value  
		Set<Map.Entry<Integer, Integer>> sortedFrequencySet = new TreeSet<Map.Entry<Integer, Integer>>(
				new Comparator<Map.Entry<Integer, Integer>>() {
					@Override
					public int compare(Map.Entry<Integer, Integer> obj1, Map.Entry<Integer, Integer> obj2) {
						int vcomp = obj1.getValue().compareTo(obj2.getValue());
						return -vcomp;
					}
				});

		//populating frequency Map.
		for (Integer integer : id) {
			if (frequencyMap.containsKey(integer)) {
				Integer val = frequencyMap.get(integer);
				frequencyMap.put(integer, ++val) ;
			} else {
				frequencyMap.put(integer, 1);
			}
		}
		System.out.println(frequencyMap);

		sortedFrequencySet.addAll(frequencyMap.entrySet());
		Map.Entry<Integer, Integer> firstKey =  sortedFrequencySet.iterator().next();
		System.out.println(" Integer " + firstKey.getKey()  + " Frequency " + firstKey.getValue());

Please refer to following interesting thread to understand sorting part...Sorting Tree by Value and not key

[Campbell Ritchie]

Good grief. What a dreadful solution.

[Wouter Oet]

Quickly created something:

/**
* List must be sorted
* @see Collecttions.sort()
**/
public static <T> T getMostOccoringElement(List<T> list) {
	int size = list.size();
	if(size == 0)
		return null;
	
	int count = 0;
	int maxCount = 0;
	T element = list.get(0);
	T mostOccuringElement = element;
	
	for(int index = 0; index<size; index++) {
		if(list.get(index).equals(element)) {
			count++;
			if(count > maxCount) {
				maxCount = count;
				mostOccuringElement = element;
			}
		} else {
			count = 1;
		}
		element = list.get(index);
	}
	return mostOccuringElement;
}

[David Newton]

Campbell Ritchie wrote:Good grief. What a dreadful solution.

I didn't even delete it like I usually do if someone provides a complete answer.

Like Wouter's complete answer--and I know he knows better :p

[Wouter Oet]

Yea I know and usually I only give abstract answers but his time it was nice to think back to my data-structure lessons and prove to myself that I still got it

[Gupta Tarun]

Campbell Ritchie wrote:Good grief. What a dreadful solution.

I Agree. I think its was an overkill if you just need the highest frequency, but okay if you need all the frequencies in descending order.
Good to know about the rules with respect to the posts getting deleted.. as I am new here.

Thanks,

[Gupta Tarun]

Wouter Oet wrote:Yea I know and usually I only give abstract answers but his time it was nice to think back to my data-structure lessons and prove to myself that I still got it

data-structure ? or you mean "Flow control"

[Campbell Ritchie]

David Newton wrote: . . . I didn't even delete it like I usually do if someone provides a complete answer. . . .

Nor did I, for the same reason.

[Anis Yusof]

Thank you gupta_tarun & wouter_oet! Both of you really helps me a lot; except both solution take a different approach. It is certainly good learning experience for me to be introduced to Map, Hashmap etc. Never heard & used of hashmap before.. :P anyway, i used wouter solution in my codes. Kinda neat & easy to understand, and it works! thanks again guys!

[Wouter Oet]

Gupta Tarun wrote:data-structure ? or you mean "Flow control"

That class also contained algorithms. So that's why I associated it with that class.