Find Duplicates

Write a function called find_dups that takes a list of int's as a parameter and returns a list of values that are duplicated in the given list. For example, if the given list contains values { 10, 20, 10, 30, 40, 20, 10 }, the list returned by your function should contain values { 10, 20 }. The order of the values in the returned list is not important, but the returned list should not contain any duplicates (i.e. the example had three 10's, but 10 shows up only once in the returned list). You will need to devise an algorithm for finding the duplicates. Suggestions will be given in class. You are free to use any member functions of the list class or functions included in the algorithm library. Once you have completed the function and tested it, determine the run-time (Big Oh) of your function. Remember to consider the run times of any library functions used as part of the solution. Explain how you arrived at the run-time, and note any assumptions you may have made regarding the run-times of any library functions.

Give your analysis of your function in file README.md.

#include #include using namespace std;

list find_dups (const list& thelist); void print_list (const list& thelist);

int main() { // A few lists for testing list list1 = { 4, 7, 1, 4, 3, 8, 9, 2 }; list list2 = { 11, 31, 22, 22, 41, 56, 55, 31, 41, 31 }; list list3 = { 4, 6, 2, 1, 3, 8, 5, 3, 1, 5, 9, 3, 4, 9, 7, 3 };

cout << "Duplicates in list1:"; print_list(find_dups(list1)); cout << "Duplicates in list2:"; print_list(find_dups(list2)); cout << "Duplicates in list3:"; print_list(find_dups(list3)); }

list find_dups (const list& thelist) { // TODO: Find all duplicates in thelist, and return those values in a list return list(); // stub code }

void print_list (const list& thelist) { // Prints a list of integers separated by spaces, with newline for (list::const_iterator i = thelist.begin(); i != thelist.end(); i++) cout << ' ' << *i; cout << endl; }