Here is the input array of int values
Example: { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 }
Find the most repeated element with its count, example output; 5 - repeated 3 times
Here is my code after some improvisations to improve the complexity from O(n)
class RepeatedEntry implements Comparable<RepeatedEntry> {
private int number;
private int count;
public void setNumber(int number) {
this.number = number;
}
public void setCount(int count) {
this.count = count;
}
public int getNumber() {
return number;
}
public int getCount() {
return count;
}
@Override
public int compareTo(RepeatedEntry obj) {
return obj.count - this.count;
}
}
public class MaxCountOfDuplicate {
public static RepeatedEntry findMostPopularItem(List<Integer> inputList) {
Collections.sort(inputList);
Set<RepeatedEntry> resultSet = new TreeSet<>();
for (int i = 0; i < inputList.size(); i++) {
int thisEle = inputList.get(i);
int lastIndexOfThisEle = inputList.lastIndexOf(thisEle);
int repeatedCount = (lastIndexOfThisEle - i) + 1;
if (repeatedCount != 1) {
RepeatedEntry repeatedEntry = new RepeatedEntry();
repeatedEntry.setNumber(thisEle);
repeatedEntry.setCount(repeatedCount);
resultSet.add(repeatedEntry);
}
}
return resultSet.iterator().next();
}
/* Given an input array find the duplicate element with max count. */
public static void main(String[] args) {
Integer[] x = { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 }; // input array
RepeatedEntry finalResult = findMostPopularItem(Arrays.asList(x));
System.out.println("Most repeated element and its count is -> \n");
System.out.println(finalResult.getNumber() + " - repeated "
+ finalResult.getCount() + " times");
}
}
Here are my relevant questions to this
I am sure the time complexity is not O(n) and O(n^2)
In this case, how do I calculate time complexity and what is it in this case?
And coming to space complexity, creating RepeatedEntry
objects in a loop, is it a performance issue?
I have assumed the input array to be Integer
wrapper, if it was strictly int
primitive, the conversions and complexity's would increase I guess. I thought of storing the result in HashMap
but avoided as it needs further processing to fetch the output, any answer using HashMap
improving complexity would help me learn too and best possible solutions as well.
inputList
), but rather the result (which should be some kind ofHashMap<T, Integer>
). \$\endgroup\$ – RobAu Oct 30 '17 at 14:25