Find the most frequent elements in an array of Integers-CodePudding

I have to find all of the elements which have the maximum frequency. For example, if array a={1,2,3,1,2,4}, I have to print as 1, also 2. My code prints only 2. How to print the second one?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define n 6
int main(){
    int a[n]={1,2,3,1,2,4};
    int counter=0,mostFreq=-1,maxcnt=0;
    for(int i=0;i<n;i  ){
        for(int j=i 1;j<n;j  ){
            if(a[i]==a[j]){
                counter  ;
            }
        }
        if(counter>maxcnt){
            maxcnt=counter;
            mostFreq=a[i];
        }
    }
    printf("The most frequent element is: %d",mostFreq);
}

CodePudding user response：

How to print the second one?

The goal it not only to print a potential 2nd one, but all the all of the elements which have the maximum frequency.

OP already has code that determines the maximum frequency. Let us build on that. Save it as int target = mostFreq;.

Instead of printing mostFreq, a simple (still O(n*n)) approach would perform the same 2-nested for() loops again. Replace this 2nd:

    if(counter>maxcnt){
        maxcnt=counter;
        mostFreq=a[i];
    }

With:

    if(counter == target){
        ; // TBD code: print the a[i] and counter.
    }

For large n, a more efficient approach would sort a[] (research qsort()). Then walk the sorted a[] twice, first time finding the maximum frequency and the 2nd time printing values that match this frequency.

This is O(n* log n) in time and O(n) in memory (if a copy of the original array needed to preserve the original). If also works well with negative values or if we change the type of a[] from int to long long, double, etc.

CodePudding user response：

The standard student solution to such problems would be this:

Make a second array called frequency, of the same size as the maximum value occurring in your data.
Init this array to zero.
Each time you encounter a value in the data, use that value as an index to access the frequency array, then increment the corresponding frequency by 1. For example freq[value] ;.
When done, search through the frequency array for the largest number(s). Optionally, you could sort it.

CodePudding user response：

We can (potentially) save some effort in an approach with unsorted data by creating an array of boolean flags to determine whether we need to count an element at all.

For the array {1, 2, 3, 1, 2, 4} we do have nested for loops, so O(n) complexity, but we can avoid the inner loop entirely for repeated numbers.

#include <stdio.h>
#include <stdbool.h>

int main(void) {
    int arr[] = {1, 2, 3, 1, 2, 4};
    size_t arr_size = sizeof(arr) / sizeof(*arr);

    bool checked[arr_size];
    for (size_t i = 0; i < arr_size; i  ) checked[i] = false;

    unsigned int counts[arr_size];
    for (size_t i = 0; i < arr_size; i  ) counts[i] = 0;

    for (size_t i = 0; i < arr_size; i  ) {
        if (!checked[i]) {
            checked[i] = true;
            counts[i]  ;
            for (size_t j = i 1; j < arr_size; j  ) {
                if (arr[i] == arr[j]) {
                    checked[j] = true;
                    counts[i]  ;
                }
            }
        }
    }

    unsigned int max = 0;
    for (size_t i = 0; i < arr_size; i  ) {
        if (counts[i] > max) max = counts[i];
    }

    for (size_t i = 0; i < arr_size; i  ) {
        if (counts[i] == max)
            printf("%d\n", arr[i]);
    }

    return 0;
}