Array with at most n duplicates

This is a discussion on Array with at most n duplicates within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by quzah It's actually even easier than that. Code: for each element in the array count occurances of ...

  1. #16
    Dae
    Dae is offline
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    Quote Originally Posted by quzah
    It's actually even easier than that.
    Code:
    for each element in the array
        count occurances of this number in the new array
        if count less than N, copy this over to the new array
    That's all folks.


    Quzah.
    Awesome, I had to define the count as static (since the value assigned to it would go away after the count occurances loop ended) and set it to 0 at the beginning of the outer loop.. but it works! /clap
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  2. #17
    Registered User
    Join Date
    Jul 2005
    Posts
    6
    Thanks for everyone's help. Based on everyone's responses, I have some semi-working code.


    Code:
    //Pass in 2 arrays of same size
    //1 filled with random numbers other with zeros
    
    int copies, new_size = 1;
    
    *(array2 + 0) = *(array1 + 0);
    
    for (int i = 1; i < size1; i++)
    {
        copies = 0;    //Reset count to 0
        for (int j = 0; j < size1; j++)
        {
            if (*(array1 + i) == *(array2 + j))
               copies++;
        }
        
        if (copies < max_dups)    //Max_dups is a constant
        {
           *(array2 + i) = *(array1 + i);
           new_size++;   
        }
    
    }
    This code gives me a new array with zeros in the unwanted slots.

    The thing I don't like about this code is that I would rather have the new array be dynamically allocated based on new_size.

    Obviously this code wouldn't work if I wanted to include zeros in my set of random numbers.

    I hope I am making sense to everyone and again thanks a bunch for the help.

    kratz

  3. #18
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Code:
    #include <cstdio>
    #define N 2
    size_t countin( int n, int array[], size_t size )
    {
        size_t ret = 0;
        for( size_t x = 0; x < size; x++ )
            if( array[ x ] == n )
                ret++;
        return ret;
    }
    
    int main( void )
    {
        int array[] = { 1, 3, 4, 5, 2, 3, 4, 1, 3, 4, 4, 3, 4, 2 };
        int newarray[ sizeof array / sizeof array[ 0 ] ] = {0};
        size_t x, y;
    
        for( y = x = 0; x < sizeof array / sizeof array[ 0 ]; x++ )
            if( countin( array[ x ], array, y ) < N )
                newarray[ y++ ] = array[ x ];
    
        for( x = 0; x < y; x++ )
            printf("newarray[ %d ] is %d\n", x, newarray[ x ] );
    
        return 0;
    }
    /*
    newarray[ 0 ] is 1
    newarray[ 1 ] is 3
    newarray[ 2 ] is 4
    newarray[ 3 ] is 5
    newarray[ 4 ] is 2
    newarray[ 5 ] is 3
    newarray[ 6 ] is 4
    newarray[ 7 ] is 1
    newarray[ 8 ] is 2
    */
    This is what I was talking about with my last post. It doesn't matter if you have zero as a valid value in this array either.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #19
    Dae
    Dae is offline
    Deprecated Dae's Avatar
    Join Date
    Oct 2004
    Location
    Canada
    Posts
    1,034
    I ended up getting sort of the same thing as kratz from quzah's comment:

    Code:
      int oldArray[] = { 19, 16, 17, 18, 17, 15, 16, 18, 17, 19, 20, 16, 15, 18, 15 };
      int tempArray[sizeof oldArray / sizeof oldArray[0]];
      
      int maxOfNum = 2;
      int static countOfNum;
      int i, j;
    
      for (i = 0; i < 15; ++i) {
        countOfNum = 0;
    
        for (j = 0; j < 15; ++j) {
          if (tempArray[j] == oldArray[i])
            ++countOfNum;
        }
    
        if (countOfNum < maxOfNum) {
          tempArray[i] = oldArray[i];
          cout << tempArray[i] << ", ";
        }
      }
    I believe it will accept 0 as a valid value too...

    If you want it the new array to be the exact size of how many are carried over, why not just make this array a temp array, then copy over the contents of the temp array to a fresh array after.

    Using my code you could do this a few ways:

    1) Use a for loop to set all the values of the tempArray to some value, ie. 666. Then after all of the code, add another for loop that counts how many of the values in tempArray != 666, that will be the size of your newArray. Then simply make a for loop (to loop amount: size of the newArray) to take the values from the tempArray and put them into the newArray.

    2) You could add another static int count and that counts inside (countOfNum < maxOfNum), which will end up being the amount of valid values in your tempArray. Then create newArray using that value as the size, then use a for loop to copy from tempArray to newArray.
    Warning: Have doubt in anything I post.

    GCC 4.5, Boost 1.40, Code::Blocks 8.02, Ubuntu 9.10 010001000110000101100101

  5. #20
    Registered User
    Join Date
    Jul 2005
    Posts
    6
    I would like to thank everyone that contributed. You guys have been a huge help.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 11-25-2008, 01:50 AM
  2. 1-D array
    By jack999 in forum C++ Programming
    Replies: 24
    Last Post: 05-12-2006, 08:01 PM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 05:15 AM
  4. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 08:48 PM
  5. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 09:31 AM

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