Spajanje u novi niz

Učitati dva sortirana niza dužine n i m.

Zadaci:

  1. int* spoji(const int* a, int n, const int* b, int m) — pravi novi niz od n + m sortiranih elemenata, u $O(n + m)$.
  2. int* jedinstveni(const int* a, int n, int& k) — pravi novi niz gde sa svaka vrednost pojavljuje jednom; njegova dužina se smešta u k.

Pitanja za razmišljanje: Ko je odgovoran za oslobađanje nizova koji vraćaju funkcije spoji i jedinstveni? Šta se dešava kada je n = m = 0?

Program mora da oslobodi memoriju koju alocira. Prevesti sa -fsanitize=address i pokrenuti:

g++ -std=c++17 -Wall -Wextra -g -fsanitize=address main.cpp

Ulaz

U prvom redu učitava se n ($0 \le n \le 10^5$), zatim n elemenata niza u rastućem poretku. Zatim se učitava m ($0 \le m \le 10^5$), zatim m elemenata niza u rastućem poretku.

Izlaz

Ispisati svih n + m brojeva, u rastućem poretku.

Zatim ispisati broj različitih vrednosti k, nakon čega ispisati : i na kraju ispisati svaku različitu vrednost jedanput.

Primer

Ulaz

4
1 3 3 8
3
2 3 9

Izlaz

1 2 3 3 3 8 9
5: 1 2 3 8 9

Postavka

main.cpp

#include <iostream>

namespace matf
{
  // TODO (1): implementirati spoji u O(n + m)
  // vraca novi niz od n + m elemenata, u rastucem poretku
  int* spoji(const int* a, int n, const int* b, int m)
  {
    return undefined;
  }

  // TODO (2): implementirati jedinstveni
  // vraca novi niz od k jedinstvenih elemenata iz a, u rastucem poretku
  int* jedinstveni(const int* a, int n, int& k)
  {
    return undefined;
  }

  void ispisi(const int* a, int n)
  {
    for (int i = 0; i < n; ++i)
      std::cout << a[i] << ' ';
    std::cout << std::endl;
  }

} // namespace matf

int main()
{
  int n;
  std::cin >> n;
  int* a = new int[n];
  for (int i = 0; i < n; ++i)
    std::cin >> a[i];

  int m;
  std::cin >> m;
  int* b = new int[m];
  for (int i = 0; i < m; ++i)
    std::cin >> b[i];

  int* c = matf::spoji(a, n, b, m);
  matf::ispisi(c, n + m);

  int k;
  int* d = matf::jedinstveni(c, n + m, k);
  std::cout << k << ": ";
  matf::ispisi(d, k);

  delete[] a;
  delete[] b;
  // TODO (3): Osloboditi zauzetu memoriju
  
  return 0;
}

Rešenje

main.cpp

#include <iostream>

namespace matf
{
  // O(n + m); vraca nov niz od n + m elemenata, a i b spojeni u rastucem redosledu. 
  int* spoji(const int* a, int n, const int* b, int m)
  {
    int* c = new int[n + m];
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
      if (a[i] <= b[j])
        c[k++] = a[i++];
      else
        c[k++] = b[j++];
    }
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];
    return c;
  }

  // O(n); a je sortiran.
  // Vraca nov niz sa svakom razlicitom vrednoscu jednom, a njegovu duzinu upisuje u k.
  int* jedinstveni(const int* a, int n, int& k)
  {
    k = 0;                                   // prvi prolaz: prebrojavanje
    for (int i = 0; i < n; ++i)
      if (i == 0 || a[i] != a[i - 1])
        ++k;

    int* d = new int[k];                     // drugi prolaz: kopiranje
    int j = 0;
    for (int i = 0; i < n; ++i)
      if (i == 0 || a[i] != a[i - 1])
        d[j++] = a[i];
    return d;
  }

  void ispisi(const int* a, int n)
  {
    for (int i = 0; i < n; ++i)
      std::cout << a[i] << ' ';
    std::cout << std::endl;
  }

} // namespace matf

int main()
{
  int n;
  std::cin >> n;
  int* a = new int[n];
  for (int i = 0; i < n; ++i)
    std::cin >> a[i];

  int m;
  std::cin >> m;
  int* b = new int[m];
  for (int i = 0; i < m; ++i)
    std::cin >> b[i];

  int* c = matf::spoji(a, n, b, m);
  matf::ispisi(c, n + m);

  int k;
  int* d = matf::jedinstveni(c, n + m, k);
  std::cout << k << ": ";
  matf::ispisi(d, k);

  delete[] a;
  delete[] b;
  delete[] c;
  delete[] d;
  return 0;
}