C# :: Aufgabe #403

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) - 18.07.2021 um 11:26 Uhr
NET 5.x; C# 9.x; VS-2019
Quellcode ausblenden C#-Code
using System;
using System.Linq;
using System.Collections.Generic;

var n1 = new int[] { 1, 2, 3 };
var n2 = new int[] { 2, 3, 7 };
var k = 3;
var s = KSmallestPairs(n1, n2, k);

Console.WriteLine(string.Join(", ", s.Select(x => "[" + string.Join(", ", x) + "]").ToList()));

static List<List<int>> KSmallestPairs(int[] n1, int[] n2, int k)
{
    List<(int sum, int a, int b)> lst = new();

    var l = k > n1.Length ? n1.Length : k;

    for (int i = 0; i < l; i++)
        for (int j = 0; j < n2.Length; j++)
            lst.Add((n1[i] + n2[j], n1[i], n2[j]));

    return lst.OrderBy(x => x.sum).Take(k).Select(x => new List<int>() { x.a, x.b }).ToList();
}