C++ :: Aufgabe #371

1 Lösung Lösung öffentlich

n kleinste Paarsummen als Array

Anfänger - C++ von JKooP - 05.06.2021 um 16:27 Uhr
Gegeben sind 2 sortierte Arrays (arr1, arr2) gleicher oder unterschiedlicher Länge
und eine Zahl (n) welche die maximale Anzahl der kleinsten auszugebenden Paarsummen vorgibt.
Jedes Array kann 1 bis zu 10.000 Zahlen der Größe +-1.000.000 beinhalten.
Der Wert für n soll nicht weniger als 1 und nicht mehr als 1.000 betragen.

Ziel soll es sein, die n kleinsten aller möglichen Paarsummen als Array zurückzugeben.

Beispiele:

arr1 = [1,2,3]; arr2 = [2,3,7]; n = 3
Lösung: [[1,2], [1,3], [2,2]], denn [1,2], [1,3], [1,7], [2,2], [2,3], [2,7], [3,2], [3,3], [3,7]
Summen: 3, 4, 8, 4, 5, 9, 5, 6, 10 => 3, 4, 4

arr1 = [1,1,2]; arr2 = [1,2,3]; n = 2
Lösung: [[1,1], [1,1]], denn [1,1], [1,2], [1,3], [1,1], [1,2], [2,3], [2,1], [2,2], [2,3]
Summen: 2, 3, 4, 2, 3, 5, 3, 4, 5

arr1 = [1,2]; arr2 = [-5]; n = 3
Lösung: [[1,-5], [2,-5]]
Summen: -4, -3

Schreibe eine Methode/Funktion, die obige Aufgabenstellung umsetzt.
Je nach Programmiersprache könne auch Vektoren, Listen, etc. verwendet werden.

Viel Spaß

Lösungen:

vote_ok
von JKooP (18070 Punkte) - 20.07.2021 um 09:40 Uhr
C++ 17
Quellcode ausblenden C-Code
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

std::vector<std::tuple<int, int, int>>KSmallestPairs(std::vector<int>n1, std::vector<int>n2, size_t k) {
    std::vector<std::tuple<int, int, int>>v;
    size_t l{ k > n1.size() ? n1.size() : k };
    for (size_t i = 0; i < l; i++)
        for (size_t j = 0; j < n2.size(); j++)
            v.push_back({ n1[i] + n2[j], n1[i], n2[j] });
    sort(v.begin(), v.end());
    v.resize(k);
    return v;
}

int main()
{
    std::vector<int>n1{ 1, 2, 3 };
    std::vector<int>n2{ 2, 3, 7 };
    size_t k{ 3 };
    auto r{ KSmallestPairs(n1, n2, k) };
    for (const auto& i : r)
        std::cout << "[" << std::get<1>(i) << ", " << std::get<2>(i) << "]\n";
}