C++ :: Aufgabe #316
1 Lösung
Median zweier zusammengefügter Arrays
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ß
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ß
Lösungen:
C++ 17
C-Code
.h
C-Code
.cpp
C-Code
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();
}
.h
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;
}