tags:

views:

155

answers:

4

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?

+2  A: 

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.

Loïc Février
+6  A: 

You've not initialized you array b. You can do it as:

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

and 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 Javascipt, 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 uninitilzed array will have garbage.

codaddict
+1 for simple solution. Although this program is still brittle in that it will crash if array a has values like {1, 600, 765, 2000, 600}
SauceMaster
+3  A: 

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";
}
FredOverflow
+1 for avoiding manual memory management if possible.
Eamon Nerbonne
Uhm, your edit is probably _technically_ fine, but given the question, I think your proposed code is overcomplicated. The questioner is still learning the basics, let's not overwhelm him with templates and iterator details just yet...
Eamon Nerbonne
Yes, `typename` is required.
Loïc Février
@Loïc: But why is it required? Isn't a name introduced by a `typedef` always a type name?
FredOverflow
Some reference : http://publib.boulder.ibm.com/infocenter/comphelp/v8v101/index.jsp?topic=/com.ibm.xlcpp8a.doc/language/ref/keyword_typename.htm
Loïc Février
@FredOverflow the `typename` applies to `value_type`, not to `map_t`. If you omit the `typename`, then `map_t::value_type` is taken as a non-type and then the compiler is granted to reject `by_second<map_t::value_type>` at the time parsing the template because `by_second` requires a type argument.
Johannes Schaub - litb
@Johannes: Of course, thanks!
FredOverflow
Would it be a bit simpler to build a `multiset` there instead of the map?
Cubbi
Yeah, that#s the classic example for a map which default-constructs an object of the referenced type upon accessing a non-existing index. Note that your algorithm will exhibit undefined behavior if the sequence passed to it is empty.
sbi
Oh, and constructing that comparator gets easier if you change it to this: `struct by_second { template <typename Pair> bool operator()(const Pair} };`
sbi
@Eamon: A task like this (well, it was counting word occurrences in a text) was among the first few my students ever had to do. Of course, by that time they could only _use_ templates, but that was fine. Manually fiddling with memory is far worse than this.
sbi
@sbi: Thanks, I updated my answer accordingly.
FredOverflow
@Fred: `most_frequent_element()` still invokes _UB_, though. However, thinking about this, since it returns an actual object of a type that's depending on a template parameter, there's probably no way around the requirement to pass it a non-empty sequence.
sbi
BTW, what's wrong with `typename std::iterator_traits<Fwd>::value_type` for the return type?
sbi
@sbi: I want to return the element and its frequency in a pair. `map<K, V>::value_type` is defined as `pair<const K, U>`.
FredOverflow
@Fred: `<slaps_forehead>` Sorry for that brainfart.
sbi
A: 

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;
}
J.F. Sebastian