0

I want to start by saying I am new to programming. I have a problem with writing a list of distinct numbers from another list in c++. Let's say I have a list l1 = {1, 12, 2, 4, 1, 3, 2} and I want to create a new list that looks like this l2 = {1, 12, 2, 4, 3}...

This is what I wrote:

#include <iostream>

using namespace std;

int main() {
    int l1[100], l2[100], length, length1 = 0, i, j, a = 0;
    cin >> length; //set the length
    for (i = 0; i < length; i++) {
        cin >> l1[i]; //add numbers to the list
    }
    l2[0] = l1[0]; //added the first number manually
    for (i = 0; i < length; i++) {
        length1++;
        a = 0;
        for (j = 0; j < length1; j++) {
            if (l1[i] != l2[j]) //this checks numbers in the second list
                a = 1;         // and if they aren't found a gets the value  
        }                     //1 so after it's done checking if a is 1 it 
        if (a == 1)          //will add the number to the list, but if the  
            l2[j] = l1[i];  //number is found then a is 0 and nothing happens,
    } //                                         SUPPOSEDLY
    for (j = 0; j < length1; j++) {
        cout << l2[j] << " ";
    }
}

The output of this is 1 -858993460 12 2 4 1 3 so obviously I did something very wrong. I'd welcome any suggestion you might have, I don't necessarily need a solution to this, I just want to get unstuck. Thanks a lot for taking time to reply to this.

Andrew
  • 13
  • 4
  • Do you actually declare `j` anywhere? Maybe I'm going crazy... – therealrootuser Aug 31 '14 at 00:50
  • Seems there's logically flaw - `for (j = 0; j < length1; j++)` do you really want to scan `l2`? – ydoow Aug 31 '14 at 00:52
  • @mattingly890 Yes, I edited my post, I am sorry I didn't notice that when i first asked my queston, I have a few other variables in my initial program that I use for menus and stuff and when I deleted those I must have accidentally deleted j. – Andrew Aug 31 '14 at 00:54
  • Why not use a `vector` instead of an array? – therealrootuser Aug 31 '14 at 00:58
  • 1
    `-858993460 = 0xCCCCCCCC` You are accessing uninitialized stack variables. I expect that at some point you are accessing an index in one of your arrays that you did not yet set with a value. – drescherjm Aug 31 '14 at 00:59
  • `length1++;` is the source of your problem. You can not increment length1 where you do. This should be the number of items in the l2 array and nothing more. – drescherjm Aug 31 '14 at 01:05
  • Is ordering important? If not, a std::set would suit your needs just fine. – Sir Digby Chicken Caesar Aug 31 '14 at 01:22
  • if all you care about is outputting distinct numbers while preserving their input order, there is no reason at all for keeping the entire initial list, then sifting through the rubble Just build it while reading input. If you want to avoid an O(N^2) algorithm you can either build it sorted or use a `std::set<>` or `std::unordered_set<>` as a lookup table while building. – WhozCraig Aug 31 '14 at 01:23
  • have a look [here](http://stackoverflow.com/questions/370195/when-and-why-will-an-os-initialise-memory-to-0xcd-0xdd-etc-on-malloc-free-new) to see why it outputs 0xCC – phuclv Aug 31 '14 at 05:42

2 Answers2

3
std::sort(l1, l1 + 100);
int* end_uniques = std::unique(l1, l1 + 100);
std::copy(l1, end_uniques, l2);
size_t num_uniques = end_uniques - l1;

This is O(N log N) instead of your O(N^2) solution, so theoretically faster. It requires first sorting the array l1 (in-place) to let std::unique work. Then you get a pointer to the end of the unique elements, which you can use to copy to l2 and of course get the count (because it may be less than the full size of 100 of course).

John Zwinck
  • 239,568
  • 38
  • 324
  • 436
0

Most Important : This solution assumes that we've to preserve order

Well....

try out this one.... I've changed identifiers a bit ( of course that's not gonna affect the execution ) It'll just help us to identify what is the sake of that variable.

Here's the code

#include <iostream>
using namespace std;

int main() 
{
    int Input[100], Unique[100], InSize, UniLength = 0;

    cin >> InSize;
    for (int ii = 0 ; ii < InSize ; ii++ ) 
    {
        cin >> Input[ii];
    }
    Unique[0] = Input[0];
    UniLength++;
    bool IsUnique;
    for ( int ii = 1 ; ii < InSize ; ii++ ) 
    {
        IsUnique=true;
        for (int jj = 0 ; jj < UniLength ; jj++ ) 
        {
            if ( Input[ii] == Unique[jj] )
            {
                IsUnique=false;
                break;
            }                     
        }                      
        if ( IsUnique )  
        {          
            Unique[UniLength] = Input[ii];
            UniLength++;
        }
    }
    for ( int jj = 0 ; jj < UniLength ; jj++ ) 
    {
        cout << Unique[jj] << " ";
    }
}

You were inserting Unique element at it's original index in new array..... and in place of those elements which were duplicate.... you was not doing any kind of shifting.... i.e. they were uninitialized..... and were giving something weird like -858993460

I appreciate above mentioned two answers but again..... I think this question was placed on hackerrank.... and unqiue_array() doesn't work there.....

Added

Of course we can only add Unique elements to our Input array..... but... this solution works..... Moreover we have 2 seconds of execution time limit.... and just 100 elements..... Keeping in mind.... that Big Oh Notation works good for really large Inputs .... Which is not case here....So there's really no point looking at time complexity....... What I'll choose is the algorithm which is easy to understand.

I hope this is what you were looking for...

Have a nice day.

The Mean Square
  • 234
  • 1
  • 9
  • You sir, are a life saver! It's everything I ever wanted. Thank you for taking time to help, and for making everything so clear. It really helps me understand more since I'm still a novice. – Andrew Aug 31 '14 at 12:02