The most frequent range of numbers in an array.

[DanielsRUS]

Hi,
I am totally new to programming and forgive me for my ignorance.
But I'm looking for code that can show me the most frequent range of numbers in an array.
Lets say there is an array with these values { 1 ,2 ,2 ,5 ,8 ,8 ,9 ,10} and the range is +-1
most frequent range of numbers would be 8-10.
Is this possible?

I only have a code that can show me the most frequent number not the range:

int a[5];
for (int i=0;i<5;i++)
   cin>>a[i];

int max_count = 0;

for (int i=0;i<5;i++)
{
   int count=1;
   for (int j=i+1;j<5;j++)
       if (a[i]==a[j])
           count++;
   if (count>max_count)
      max_count = count;
}

for (int i=0;i<5;i++)
{
   int count=1;
   for (int j=i+1;j<5;j++)
       if (a[i]==a[j])
           count++;
   if (count==max_count)
       cout << a[i] << endl;
}

[jonnin]

why isnt the most frequent from 2 to 8?
is the range from the VALUE or the DATA? If its from the value, 5+1 and 5-1 isnt a range, ok. If its from the data (location), 5+1 is the 8s and 5-1 is the 2s. So I guess the answer is its off the value, but I want to confirm that.

is there a known max and min value for the data? That is, do you know to stop looking at 10, or 20, or 1000 or something? That would make it easier.

as it stands one way is to store value & count pairs in a map. Then you can iterate back over those looking at the counts against the range to see where the max set is (if any, be prepared to handle the answers of 0, 1, and many results).

[lastchance]

@DanielsRUS,
Maybe I'm slow, but it took me a long time to realise from your description what you were looking for.If presented with an array { 1 ,2 ,2 ,5 ,8 ,8 ,9 ,10} my immediate reaction is that the single RANGE is 9 (i.e. 10 subtract 1).

I think what you are actually looking for is the "interval of length 2 with the most array elements in". This is the interval [8 to 10] in this example, but, in principle, there may actually be several intervals with the maximum frequency.

Consider how you might do it by hand (or eye). Let's assume that the array is sorted in ascending order. (There's nothing in your code to enforce that, but you could use std::sort in <algorithm> if necessary.) It's unclear whether there are any restrictions on what values you may have in your array, but I'll assume not.


Here's one possible route: I'm sure there are better ones.

Take the first element (1). This could be in several length-2 intervals: [-1 to 1], [0 to 2] or [1 to 3]. The best of these has a frequency of 3 elements.

Take the next element (2). This could be in several length-2 intervals: [0 to 2], [1 to 3] or [2 to 4]. The best of these has a frequency of 3 elements.

And so on .... until the last element. The best will be a frequency of 4, for the interval [8 to 10] when you are looking at values of 8, 9 or 10.


One method, then, would be to keep those frequencies in a second, parallel array b[] ... when you've finished scanning you use your existing type of code to find the maximum element of b[]. Note that there could, in principle, be more than one of these "modes".

An alternative, probably better, method could be to keep track of the highest frequency as you go along, assigning some indicator of the best interval so far (for example, its left-hand end) to a std::set. When a new best interval is found the set is cleared before the new interval indicator is assigned to it. std::set would have an advantage because it keeps unique elements only and will sort them for you.

A third method would be to make two passes: the first to find the best frequency and the second to write the corresponding intervals out.


It actually looks quite an interesting problem, so choose an algorithm and try to put it together ... in bits, testing each as you go along.