Median zweier zusammengefügter Arrays

1 Lösung

#316

Fortgeschrittener - C++ von JKooP - 21.11.2020 um 07:46 Uhr

Es soll der Median (Zentralwert) eines sortierten Arrays,
das aus zwei (beliebig großen) zusammengefügten sortierten Arrays besteht, ermittelt werden.

Beispiele:
arr1 = [1, 3] arr2 = [2]
mergeSorted = [1, 2, 3] -> Median = 2

arr1 = [2, 4] arr2 = [1, 3]
mergeSorted = [1, 2, 3, 4] -> Median = 2.5
(wenn kein Zentralwert vorhanden ist, dann wird das arithmetische Mittel der beiden mittleren Zahlen ermittelt)
-> (2+3) / 2 = 2.5

Weitere Beispiele:
[0, 0] [0, 0] -> 0
[] [4] -> 4
[3] [] -> 3
[] [] -> 0
[-4, 4] [-2, 1] -> [-4, -2, 1, 4] -> -0.5

Fortgeschrittene können die Funktion/Methode dahingehend erweitern,
sodass sowohl mindestens 2 Arrays aufgenommen werden,
als auch auch ein Array bzw. eine Liste von Arrays verarbeitet werden kann.

Viel Spaß

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von JKooP (18090 Punkte) - 24.04.2021 um 22:49 Uhr

C++ 17

C-Code

#include "median.h"

int main()
{
    vector<int> v1{ -1, 1, 2, 3, 4 };
    vector<int> v2{ -1, 0, 1, 2, 5 };
    median m{ v1, v2 };

    std::cout << m.get_median();
}

C-Code

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class median
{
private:
	vector<int> v1_, v2_, v3_;
	int get_center();
	vector<int> get_concat_sorted_vector();
	
public:
	median(vector<int> v1, vector<int> v2) :v1_{ v1 }, v2_{ v2 }, v3_{ get_concat_sorted_vector() }{}
	double get_median();
};

.cpp

C-Code

#include "median.h"

int median::get_center()
{
    return (int)floor(v3_.size() / 2.0);
}

vector<int> median::get_concat_sorted_vector()
{
    auto vt{ v1_ };
    vt.insert(vt.end(), v2_.begin(), v2_.end());
    sort(vt.begin(), vt.end());
    return vt;
}

double median::get_median()
{
    auto m{ 0.0 };

    if (v3_.size() == 0)
        m = 0;
    else if (v3_.size() % 2 != 0)
        m = v3_[get_center()];
    else
        m = (v3_[get_center() - 1] + v3_[get_center()]) / 2.0;

    return m;
}