CODEWITHSUNDEEP
javaarraysfind
Les Paul
Les Paul

Reputation: 209

How to find the most frequently repeated number in Array?

I know there are similar questions like this one. But here's a trick. Let's assume that we have this array:

int[] list = {1, 2, 3, 1, 0, 0, 0, 5, 6, 1569, 1, 2, 3, 2, 1569, 3};

System.out.println("Most repeated value is: " + ???);    

/* Now As you can see 0's, 1's, 2's and 3's has the same frequency "3 times". In this case, 
   I need to print the smallest number which is the most frequently repeated. So that, 
   prompt should be 0 */

To make it more understandable:

// All the digits except 5 and 6 and 1569's rest of the values repeated 3 times. I have to
// print the smallest number which occurs most.

If you could show me a solution code wise in java I would very appreciate it. Thanks for checking.

Upvotes: 1

Views: 4236

Answers (2)

Ross H Mills III
Ross H Mills III

Reputation: 311

    public static void main(String args[]) {
    int[] list = {1, 2, 3, 1, 0, 0, 0, 5, 6, 1569, 1, 2, 3, 2, 1569, 3};

    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for (Integer nextInt : list) {
        Integer count = map.get(nextInt);
        if (count == null) {
            count = 1;
        } else {
            count = count + 1;
        }
        map.put(nextInt, count);
    }

    Integer mostRepeatedNumber = null;
    Integer mostRepeatedCount = null;
    Set<Integer>keys = map.keySet();
    for (Integer key : keys) {
        Integer count = map.get(key);
        if (mostRepeatedNumber == null) {
            mostRepeatedNumber = key;
            mostRepeatedCount = count;
        } else if (count > mostRepeatedCount) {
            mostRepeatedNumber = key;
            mostRepeatedCount = count;
        } else if (count == mostRepeatedCount && key < mostRepeatedNumber) {
            mostRepeatedNumber = key;
            mostRepeatedCount = count;
        }
    }

    System.out.println("Most repeated value is: " + mostRepeatedNumber);    

}

will give the following output ...

Most repeated value is: 0

Upvotes: 2

Steve
Steve

Reputation: 11963

I guess I don't have to mention the O(n^2) algorithm.

The average O(n) algorithm:

int maxCount = 0;
int maxKey = -1;
foreach element in array
{
  if(hashTable contains element)
  {
     increase the count;
     if (count > maxCount)
     {
        maxCount = count;
        maxKey = element
     }
     else if (count == maxCount && maxKey > element)
     {
        maxKey = element;
     }
  }
  else
  {
     insert into hash Table with count 1;
     if (1> maxCount)
     {
        maxCount = 1;
        maxKey = element
     }
  }
}

O(n) + k algorithm: same idea make an array with length = max value in the array instead of hashTable, and do array[element]++;

Upvotes: 1

Related Questions