find most occurence element in array

Question

Here is simple program to find the element which occurs most often in an array:

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char *argv[]) {
    int a[] = {1,2,3,4,4,4,5};
    int n = sizeof(a) / sizeof(int);
    int max = 0;
    int result = 0;
    int *b = new int[n];
    for (int i = 0;  i < n;  i++) {
        b[a[i]] = (b[a[i]] || 0) + 1;
        if (b[a[i]] > max) {
            max = b[a[i]];
            result = a[i];
        }
    }
    cout << result << endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

But it doesn't work; it prints 1. Why?

Answer 1

Since you are including vector anway, why not replace int *b=new int [n]; with std::vector<int> b(n)? This also takes care of releasing the memory, you forgot to delete[] b.

But as others have mentioned, your solution will break if the array contains elements larger than n. A better approach might be to count the elements with a mapping to int. That way, you can also count elements that cannot be used as an array index, for example strings.

There is also no reason to limit ourselves to arrays. Here is a generic solution that works with any container of any less-than comparable element type:

#include <algorithm>
#include <iterator>
#include <map>

struct by_second
{
    template <typename Pair>
    bool operator()(const Pair& a, const Pair& b)
    {
        return a.second < b.second;
    }
};


template <typename Fwd>
typename std::map<typename std::iterator_traits<Fwd>::value_type, int>::value_type
most_frequent_element(Fwd begin, Fwd end)
{
    std::map<typename std::iterator_traits<Fwd>::value_type, int> count;

    for (Fwd it = begin; it != end; ++it)
        ++count[*it];

    return *std::max_element(count.begin(), count.end(), by_second());
}

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> test {1, 2, 3, 4, 4, 4, 5};
    std::pair<int, int> x = most_frequent_element(test.begin(), test.end());
    std::cout << x.first << " occured " << x.second << " times";
}

Answer 2

You've not initialized your array b. You can do it like this:

int *b=new int [n]();
                  ^^

Once that is done you can increment your frequency array as:

b[a[i]]++;

in place of

b[a[i]]=(b[a[i]]||0)+1;

Your way of doing (b[a[i]]||0)+1 works in languages like Javascript, Perl where an un-initialized array element will have a special value called undef or null. C++ does not have anything like that and an uninitialized array will have garbage.

Answer 3

You need to initialize your array b to zero.

 b[a[i]]||0

will not work, you don't know what is in b originally.

Shorter code :

int main(int argc, char *argv[])
{
    int a[]={1,2,3,4,4,4,5};
    int n = sizeof(a)/sizeof(int );
    int *b=new int [n];
    fill_n(b,n,0); // Put n times 0 in b

    int val=0; // Value that is the most frequent
    for (int i=0;i<n;i++)
        if( ++b[a[i]] >= b[val])
            val = a[i];

    cout<<val<<endl;
    delete[] b;
    return 0;
}

ATTENTION : your code (mine too) can ONLY work if the maximum value is lower than the number of values in the array a.

If that's not the case and the maximum value is much greater that the number of elements, you might want to sort the array and then search in linear time (and constant space) for the maximum value.

Answer 4

implementation that takes advantage of the fact map is sorted.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

template<class T> pair<T, int> getSecondMostOccurance(vector<T> & v) {
    map<T, int> m;

    for ( int i = 0; i < v.size(); ++i ) {
        m[ v[i] ]++;
    }
    return *m.end();
}

int main() {
    int arr[] = {1, 4, 5, 4, 5, 4};
    pair<int, int> p = getSecondMostOccurance(vector<int>(arr, arr+7));
    cout << "element: " << p.first << " count: " << p.second << endl;
    return 0;
}

Answer 5

Here, O(n) in time, O(1) in space general solution that works on sorted ranges.

#include <iostream>

template <class ForwardIterator>
ForwardIterator
most_common(ForwardIterator first, ForwardIterator last) {
  /** Find the most common element in the [first, last) range.

      O(n) in time; O(1) in space.

      [first, last) must be valid sorted range.
      Elements must be equality comparable.
  */
  ForwardIterator it(first), max_it(first);
  size_t count = 0, max_count = 0;
  for ( ; first != last; ++first) {
    if (*it == *first) 
      count++;
    else {
      it = first;
      count = 1;
    }      
    if (count > max_count) {
      max_count = count;
      max_it = it;
    }
  }  
  return max_it;
}    
int main() {
  int a[] = {1, 2, 3, 4, 4, 4, 5};
  const size_t len = sizeof(a) / sizeof(*a);
  std::cout << *most_common(a, a + len) << std::endl;
}