having trouble with searching an array..

This is a discussion on having trouble with searching an array.. within the C Programming forums, part of the General Programming Boards category; My problem involves writing a function that takes an integer array and an index as arguements, and returns the value ...

  1. #1
    Registered User
    Join Date
    Jan 2007
    Posts
    5

    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...

  2. #2
    Registered User
    Join Date
    Jan 2007
    Posts
    5
    ps, the original array can not be altered

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    > (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];
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    5

    im still not sure about this...

    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?

  5. #5
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    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
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  6. #6
    Registered User
    Join Date
    Jan 2007
    Posts
    5
    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

  7. #7
    Registered User
    Join Date
    Jan 2007
    Posts
    5
    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.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    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?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Eager young mind
    Join Date
    Jun 2006
    Posts
    342
    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?
    In the middle of difficulty, lies opportunity

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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);
    Last edited by robatino; 01-21-2007 at 06:55 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 08:51 AM
  2. Type and nontype parameters w/overloading
    By Mr_LJ in forum C++ Programming
    Replies: 3
    Last Post: 01-02-2004, 12:01 AM
  3. Array Program
    By emmx in forum C Programming
    Replies: 3
    Last Post: 08-31-2003, 12:44 AM
  4. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM
  5. searching thru a c++ class array
    By stanleyw in forum C++ Programming
    Replies: 1
    Last Post: 05-29-2002, 09:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21