having trouble with searching an array..

My problem involves writing a function that takes an integer array and an index as arguements, and returns the value of the integer in the array that appears most frequently, only that if there are 2 or more values with the same frequency, the smallest should be returned.

I have been able to get this far:

Code:

---


void find_maxfreq(int A[], int index) {
        int i=0, j=0, maxfreq=1, freq=1, number=0;
        int numbers[MAXVALS];

        for (i=0 ; i<index; i++) {
                for (j=i+1; j<index; j++) {
                        if (A[i]==A[j]) {
                                freq++;
                        }
                }
                if (freq>=maxfreq) {
                        maxfreq = freq;
                        number = A[i];
                        freq = 1;                       
                }
        }
                printf("Max freq : %d\n", maxfreq);
                printf("Value : %d\n", number);
        return;
}

---

this works great, but does not work for the last condition for the return of the smallest value when there are similar frequencies. I feel it may be neccessary to include another array to do this. Could anybody shed some light on this for me...

ps, the original array can not be altered

> (freq>=maxfreq)
You need two cases

If it's >, then do what you do now

If it's =, then update number with the smaller of number and A[i];

I applied the solution and tested the function :

Code:

---



void find_maxfreq(int A[], int index) {
        int i=0, j=0, maxfreq=1, freq=1, number=0;

        for (i=0 ; i<index; i++) {
                for (j=i+1; j<index; j++) {
                        if (A[i]==A[j]) {
                                freq++;
                        }
                }
                if (freq>maxfreq) {
                        maxfreq = freq;
                        number = A[i];
                        freq = 1;                       
                }
                if (freq==maxfreq) {
                        if (A[i]<number)
                                number = A[i];
                        else
                                number = number;
                        }
                }       
        printf("Max freq : %d\n", maxfreq);
        printf("Value : %d\n", number);
        return;
}

---

with input : 4 4 4 4 3 3 3 6 6 6
output:

Max freq : 6
Value : 3

as the input shows, the maximum frequency was 4 with 4 repeats. whats going wrong?

you forgot to reset the freq to 1 on each iteration of the first loop

try to use the smallest skope possible for each of your vars

cheers vart, and thanks salem. sure our paths will cross again. im such a noob. btw, I barely understand scope with variables, could you be more specific to this example

final code:

Code:

---

void find_maxfreq(int A[], int index) {
        int i=0, j=0, maxfreq=1, freq=1, number=0;

        for (i=0 ; i<index; i++) {
                for (j=i+1; j<index; j++) {
                        if (A[i]==A[j]) {
                                freq++;
                        }
                }
                if (freq>maxfreq) {
                        maxfreq = freq;
                        number = A[i];
                        freq = 1;                       
                }
                if (freq==maxfreq) {
                        if (A[i]<number) {
                                number = A[i];
                                freq = 1;
                        }
                        else {
                                number = number;
                                freq = 1;
                        }
                }
                freq = 1;       
        }       
        printf("Max freq : %d\n", maxfreq);
        printf("Value : %d\n", number);
        return;
}

---

working.

How many freq = 1; do you really need?
Which one is always executed regardless of whatever condition is true?

> if (freq==maxfreq)
If the previous if() was true, does this get executed as well?
Does it need to be executed?

I was thinking of someway to optimize the solution. What we have is an O(n*2) method.
Suppose I am allowed to use extra space, I can traverse the array once to find out the value of the largest number.Then,I can create another array whose size is as big as this number.

Code:

---

  // let k be the largest number
  //  n is the size of the given array
 ...
 ...

 int C[k];
 for(i=0;i<k;i++)
      C[i]=0;

  for(i=0;i<n;i++)
      {
          C[A[i]]++;
      }
 
  ...
  ...

---

So,the value of C[i] is now the number of times the number "i" is seen in the array A.
One more traversal on the array C to give me the number that is needed.

The complexity is something like :
n - for the traversal to find the largest element. (plus)
k - for the for loop where we set each element of C to be 0 (plus)
k - for the actual loop. (plus)
k - for the last traversal

( k can be greater than n)

so, this gives me a linear solution, but at the price of using the extra array of size k.
Is there a better method of getting this done in linear time?

You can sort the array in O(N log N) time using qsort() (or sort() in C++), then find the smallest of those elements with the highest frequency in a single O(N) sweep.

Edit: Of course you have to copy the array first and sort the copy, since the original can't be altered.

Edit: I just checked and it appears that qsort() uses Quicksort which has worst case time O(N^2) although its average time is supposed to be O(N log N). C++'s sort() has O(N log N) worst case time so you might consider using that, or implementing your own sort. C++'s sort also has a default comparison operator which does the right thing in this case so you can just call it as

Code:

---

sort(array, array + N);

---