Obriši sva pojavljivanja

Napisati funkciju

template <typename T>
void obrisi_sve(DinamickiNiz<T>& a, const T& x);

koja iz niza a briše sva pojavljivanja vrednosti x, uz očuvanje redosleda ostalih elemenata, u vremenu $O(n)$. Koristi se klasa DinamickiNiz<T> iz zaglavlja dinamicki_niz.h.

Pitanja za razmišljanje: Koja je složenost rešenja koje za svako pojavljivanje poziva obrisi(i)? Šta se dešava pri pozivu obrisi_sve(a, a[0])?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 2 \cdot 10^5)$, a zatim n celih brojeva. Nakon toga učitava se ceo broj x.

Izlaz

U prvom redu ispisati niz posle poziva obrisi_sve(a, x). Zatim, ako niz nije prazan, pozvati obrisi_sve(a, a[0]) i u drugom redu ispisati niz (ako je niz prazan, drugi red je prazan).

Primer

Ulaz

8
1 2 7 2 3 2 7 1
2

Izlaz

1 7 3 7 1
7 3 7

Postavka

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Brise sva pojavljivanja vrednosti x iz niza, uz ocuvanje redosleda
    // ostalih elemenata, u vremenu O(n).
    template <typename T>
    void obrisi_sve(DinamickiNiz<T>& a, const T& x)
    {
        // Ovde ide vasa implementacija
    }

} // namespace matf

template <typename T>
void ucitaj(DinamickiNiz<T>& niz)
{
    std::size_t n;
    std::cin >> n;
    for (std::size_t i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        niz.dodaj(x);
    }
}

template <typename T>
void ispisi(const DinamickiNiz<T>& niz)
{
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        std::cout << niz[i] << " ";
    std::cout << std::endl;
}

int main()
{
    DinamickiNiz<int> a;
    ucitaj(a);

    int x;
    std::cin >> x;

    matf::obrisi_sve(a, x);
    ispisi(a);

    if (!a.prazan())
        matf::obrisi_sve(a, a[0]);
    ispisi(a);

    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Brise sva pojavljivanja vrednosti x iz niza, uz ocuvanje redosleda
    // ostalih elemenata, u vremenu O(n).
    template <typename T>
    void obrisi_sve(DinamickiNiz<T>& a, const T& x)
    {
        // x moze biti element niza a (npr. obrisi_sve(a, a[0])), a taj
        // element se prepisuje tokom prolaza, pa se vrednost pamti unapred.
        T vrednost = x;

        // Elementi koji ostaju se redom prepisuju na pocetak niza; k je broj
        // do sada zadrzanih elemenata. Svaki element se pomera najvise jednom.
        std::size_t k = 0;
        for (std::size_t i = 0; i < a.velicina(); ++i) {
            if (!(a[i] == vrednost)) {
                a[k] = a[i];
                ++k;
            }
        }

        // Ukupno O(n), jer je svako obrisi_poslednji O(1). Pozivi obrisi(i)
        // u prvoj petlji bi dali O(n^2).
        while (a.velicina() > k)
            a.obrisi_poslednji();
    }

} // namespace matf

template <typename T>
void ucitaj(DinamickiNiz<T>& niz)
{
    std::size_t n;
    std::cin >> n;
    for (std::size_t i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        niz.dodaj(x);
    }
}

template <typename T>
void ispisi(const DinamickiNiz<T>& niz)
{
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        std::cout << niz[i] << " ";
    std::cout << std::endl;
}

int main()
{
    DinamickiNiz<int> a;
    ucitaj(a);

    int x;
    std::cin >> x;

    matf::obrisi_sve(a, x);
    ispisi(a);

    if (!a.prazan())
        matf::obrisi_sve(a, a[0]);
    ispisi(a);

    return 0;
}