The Algorithm Design Manual (3rd) Exercise Solution 'E4-12'

Table of Contents

Introduction
Repository
Exercise 4-12
- Question
- Solution
  - Subproblem (a)
    - Outline
    - Code
  - Subproblem (b)
    - Outline
    - Code

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 4-12

Question

Give an efficient algorithm to compute the union of sets A and B, where $n = max(|A|, |B|)$ . The output should be an array of distinct elements that form the union of the sets. (a) Assume that A and B are unsorted arrays. Give an $O(n log n)$ algorithm for the problem. (b) Assume that A and B are sorted arrays. Give an $O(n)$ algorithm for the problem

Solution

Subproblem (a)

Outline

Combine set A and B into new array C (not 'set').
Sort C such that duplicate value can be detected quickly.
Remove duplicates and create new set.

Code

// Combine set A and B into new array C (not 'set')
// Sort C such that duplicate value can be detected quickly
// Remove duplicates and create new set

#include <algorithm>
#include <cassert>
#include <unordered_set>
#include <vector>

std::unordered_set<int> create_union(const std::unordered_set<int>& s1,
                                     const std::unordered_set<int>& s2) {
    std::vector<int> v_comb{s1.cbegin(), s1.cend()};
    v_comb.insert(v_comb.end(), s2.cbegin(), s2.cend());

    std::sort(v_comb.begin(), v_comb.end());

    auto it_last{std::unique(v_comb.begin(), v_comb.end())};
    v_comb.erase(it_last, v_comb.end());
    return {v_comb.cbegin(), v_comb.cend()};
}

int main(int argc, char const* argv[]) {
    assert(create_union({1}, {1}) == (std::unordered_set<int>{1}));
    assert(create_union({1}, {2}) == (std::unordered_set<int>{1, 2}));
    assert(create_union({1, 2, 3}, {4, 5, 6}) ==
           (std::unordered_set<int>{1, 2, 3, 4, 5, 6}));
    assert(create_union({1, 2, 2, 3, 3}, {4, 5, 6}) ==
           (std::unordered_set<int>{1, 2, 3, 4, 5, 6}));
    assert(create_union({1, 2, 2, 3, 3}, {2, 3, 4}) ==
           (std::unordered_set<int>{1, 2, 3, 4}));
    assert(create_union({1, 2, 2, 3, 3}, {3, 3, 2, 2, 1}) ==
           (std::unordered_set<int>{1, 2, 3}));
    return 0;
}

Subproblem (b)

Outline

Use the same procedure as used in merge logic in mergesort.

Pick smallest element from one of the top of sorted arrays and repeat this until one of them becomes empty
Ignore duplicate values in merging

Code

// Use the same procedure as used in merge logic in mergesort
//  - Pick smallest element from one of the top of sorted arrays
//      and repeat this until one of them becomes empty
//  - Ignore duplicate values in merging
#include <algorithm>
#include <cassert>
#include <vector>

std::vector<int> create_union(const std::vector<int>& v1,
                              const std::vector<int>& v2) {
    std::vector<int> result;
    auto it_v1{v1.cbegin()};
    auto it_v2{v2.cbegin()};
    while (it_v1 != v1.cend() && it_v2 != v2.cend()) {
        if (*it_v1 < *it_v2) {
            if (result.empty() || result.back() != *it_v1)
                result.push_back(*it_v1);
            ++it_v1;
        } else {
            if (result.empty() || result.back() != *it_v2)
                result.push_back(*it_v2);
            ++it_v2;
        }
    }
    if (it_v1 != v1.cend()) {
        if (result.back() == *it_v1) ++it_v1;
        result.insert(result.end(), it_v1, v1.cend());
    }
    if (it_v2 != v2.cend()) {
        if (result.back() == *it_v2) ++it_v2;
        result.insert(result.end(), it_v2, v2.cend());
    }
    return result;
}

// For check an array sorted and unique
std::vector<int> checked_sorted_unique(const std::vector<int>& v) {
    std::vector<int> cp_v{v};
    std::sort(cp_v.begin(), cp_v.end());
    auto it_last{std::unique(cp_v.begin(), cp_v.end())};
    cp_v.erase(it_last, cp_v.end());
    assert(v == cp_v);
    return v;
}

int main(int argc, char const* argv[]) {
    assert(create_union(checked_sorted_unique({1}),
                        checked_sorted_unique({1})) == (std::vector<int>{1}));
    assert(
        create_union(checked_sorted_unique({1}), checked_sorted_unique({2})) ==
        (std::vector<int>{1, 2}));

    assert(create_union(checked_sorted_unique({1, 2, 5, 6}),
                        checked_sorted_unique({1, 2, 5, 6})) ==
           (std::vector<int>{1, 2, 5, 6}));
    assert(create_union(checked_sorted_unique({1, 2, 3}),
                        checked_sorted_unique({4, 5, 6})) ==
           (std::vector<int>{1, 2, 3, 4, 5, 6}));
    assert(create_union(checked_sorted_unique({1, 2, 3, 4}),
                        checked_sorted_unique({3, 4, 5, 6})) ==
           (std::vector<int>{1, 2, 3, 4, 5, 6}));
    assert(create_union(checked_sorted_unique({1, 5, 10, 15}),
                        checked_sorted_unique({2, 4, 6, 8, 10, 12, 14, 16})) ==
           (std::vector<int>{1, 2, 4, 5, 6, 8, 10, 12, 14, 15, 16}));
    return 0;
}