Duplicate Values in a list

[restive crater]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For more information use !howto ask.

[worthy barn]

as you can see, its sort of working well

[queen quail]

are the lists guaranteed to be sorted?

[worthy barn]

yes

lists are guaranteed to be sorted with no duplicates individually

[queen quail]

Incrementing both iter1 and iter2 during each iteration cannot be right

If your first list was {1} and your second list was {2}, how do you get the union {1, 2} using your function?

[worthy barn]

it would go to the first if statement and push 1 in to the result then 2

[queen quail]

I'm afraid not

Let's dissect line-by-line

Oh wait

I'm dumb

I did not see you were doing both inserts in one if statement

[worthy barn]

yea 🙂

[queen quail]

Okay new question then

What happens if lists are of different size?

[worthy barn]

thats what im trying to figure out, because they are and thats where my issue comes out.

my first guess is to change the while loop to OR

[queen quail]

Oh I thought your issue was with shared elements

Yeah OR would help

Are you familiar with merge sort?

[worthy barn]

sorry, yeah shared elements in array of different length

Yea, somewhat

but, for this situation dont think i would need to do that

[queen quail]

What's this for? HW?

[worthy barn]

m trying to reach a O(m+n)

yea

[queen quail]

If you look into merge sort, you'll find how it merges two sorted lists into one sorted list.

Works even if the two lists are of different size.

And since the new list will be sorted, you can modify it to track if a duplicate element will be added, and then skip adding that element.

[worthy barn]

if i sort though wont i be exceeding the O(m+n)?

i cant think of a more efficient solution

[worthy barn]

anyone have an idea? or maybe a bit more guidance on what merge sort hes mentioning?

[queen quail]

You're merging two already-sorted merged lists

Which is O(m+n)

[tight flame]

Rather than list, consider using set.
Because it would seem that both input lists to this function were ordered and unique anyway.

[cinder elk]

#include <iostream>
#include <list>
using namespace std;

void helperFuncAdd(list<int>& result, list<int>::const_iterator& iter)
{
    if( result.empty() || *iter != *(result.rbegin()) )
    {
        result.push_back(*iter); 
    }
    ++iter;
}

void doUnion(const list<int>& list1, const list<int>& list2, list<int>& result)
{
    result.clear();
    list<int>::const_iterator iter1;
    list<int>::const_iterator iter2;

    iter1 = list1.begin();
    iter2 = list2.begin();

    while(iter1 != list1.end() && iter2 != list2.end())
    {
        if(*iter1 < *iter2){
            helperFuncAdd(result, iter1);
        } else {
            helperFuncAdd(result, iter2);
        }
    }
     
     while(iter1 != list1.end())
     {
         helperFuncAdd(result, iter1);
     }
     
    while(iter2 != list2.end())
     {
         helperFuncAdd(result, iter2);
     }
        
}

int main() {
    
    list<int> list1 = {1,1,1,1,3,3,3,3};
    list<int> list2 = {2,2,2,2,4,4,4,4};
    
    list<int> sortedUnion;
    doUnion(list1, list2, sortedUnion);
    
    for(int elem : sortedUnion)
    {
        cout<<elem<<endl;    
    }
    
    return 0;
}

[formal dome]

@cinder elk, your formatted code (missing deletion permissions):

#include <iostream>
#include <list>
using namespace std;

void helperFuncAdd(list<int>& result, list<int>::const_iterator& iter) {
    if (result.empty() || *iter != *(result.rbegin())) {
        result.push_back(*iter);
    }
    ++iter;
}

void doUnion(const list<int>& list1,
             const list<int>& list2,
             list<int>& result) {
    result.clear();
    list<int>::const_iterator iter1;
    list<int>::const_iterator iter2;

    iter1 = list1.begin();
    iter2 = list2.begin();

    while (iter1 != list1.end() && iter2 != list2.end()) {
        if (*iter1 < *iter2) {
            helperFuncAdd(result, iter1);
        } else {
            helperFuncAdd(result, iter2);
        }
    }

    while (iter1 != list1.end()) {
        helperFuncAdd(result, iter1);
    }

    while (iter2 != list2.end()) {
        helperFuncAdd(result, iter2);
    }
}

int main() {
    list<int> list1 = {1, 1, 1, 1, 3, 3, 3, 3};
    list<int> list2 = {2, 2, 2, 2, 4, 4, 4, 4};

    list<int> sortedUnion;
    doUnion(list1, list2, sortedUnion);

    for (int elem : sortedUnion) {
        cout << elem << endl;
    }

    return 0;
}

[restive crater]

This question thread is being automatically closed. If your question is not answered feel free to bump the post or re-ask. Take a look at !howto ask for tips on improving your question.

[restive crater]

@worthy barn

This question thread is being automatically marked as solved.