Find an element of most elements in an array

Question

Here is a simple program to find the element that is most often found in the 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 this does not work; he prints 1 . Why?

Answer 1

Since you turn on the vector at night, why not replace int *b=new int [n]; on std::vector<int> b(n) ? This also applies to freeing memory, you forgot delete[] b .

But, as others have already said, your solution will break if the array contains elements larger than n. A better approach might be counting elements with matching with int. That way, you can also count elements that cannot be used as an index to an array, such as a string.

There is also no reason to limit yourself to arrays. Here is a general solution that works with any container of any type, less comparable 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 did not initialize array b . You can do it as follows:

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

Once this is done, you can increase your frequency array as follows:

 b[a[i]]++; 

instead

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

Your way of doing (b[a[i]]||0)+1 works in languages ​​such as Javascript , Perl, where an uninitialized array element will have the special value undef or null . C ++ has nothing of the kind, and an uninitialized array will have garbage .

Answer 3

You need to initialize array b to zero.

  b[a[i]]||0 

will not work, you do not know what was originally from the beginning.

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 less than the number of values ​​in array a.

If this is not the case and the maximum value is much larger than the number of elements, you can sort the array and then search in linear time (and in constant space) for the maximum value.

Answer 4

Here O (n) in time, O (1) in the space of a 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; } 

Answer 5

using a fact map, 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; }