Написано: 23.03.2023

C. Слияние двух последовательностей

Задание было предложено на тесте в комании Яндекс.

Задание.

Даны две отсортированные последовательности.

Нужно выполнить слияние так, чтобы не было дублей.

Пример 1.

Входные данные: a = {1,1,2,2,4,5}, b = {3,7,8}

Результат: {1,2,3,4,5,7,8}

Пример 2.

Входные данные: a = {1,1,2,2,4,5}, b = {}

Результат: {1,2,4,5}

Решение.

class Solution {
public:
    vector<int> merge(vector<int>& a, vector<int>& b) {
        vector<int> res;
        int n = a.size(), m = b.size(), i = 0, j = 0, candidat;

        while(i < n || j < m) {
            if(i == n) {
                candidat = b[j++];
            } else if (j == m) {
                candidat = a[i++];
            } else if(a[i] == b[j]) {
                candidat = a[i++];
                j++;
            } else if(a[i] < b[j]) {
                candidat = a[i++];
            } else {
                candidat = b[j++];
            }

            if(res.size() == 0 || res.back() != candidat) {
                res.push_back(candidat);
            }
        }

        return res;
    }
};