I need to create a function with below specification:
- it takes two lists of ints as input and outputs list of tuples <int?, int?>,
- the structure of the tuple must be either (a, a), (a, null) or (null, a),
- the order of the tuples in the result list is irrelevant.
Cases:
Case 1
Input: [] , []
Output: []
Case 2
Input: [4, 2, 3, 1 ] , [ 1, 2, 3, 4]
Output: [(4,4), (2,2), (3,3), (1,1)]
Case 3
Input: [4, 2, 3, 1] , []
Output: [(4, null), (2,null), (3,null), (1,null)]
Case 4
Input: [] , [ 1, 2, 3, 4 ]
Output: [(null, 1), (null,2), (null,3), (null,4)]
Case 5
Input: [ 1, 2, 5] , [ 1, 2, 3, 4]
Output: [(1, 1), (2,2), (5,null), (null,3), (null,4)]
My implementation (C#)
Below is my implementation of the Function and it seems to work. However, it seems not to be very optimal and I am searching for a better approach.
internal static List<Tuple<int?, int?>> PairInts(List<int> firstList, List<int> secondList)
{
List<Tuple<int?, int?>> pairs = new List<Tuple<int?, int?>>();
List<int> firstListBackup = new List<int>(firstList);
List<int> secondListBackup = new List<int>(secondList);
foreach (int val in firstList)
{
foreach (int val2 in secondList)
{
if (val == val2)
{
pairs.Add(new Tuple<int?, int?>(val, val2));
firstListBackup.Remove(firstListBackup.Where(v => v == val).FirstOrDefault());
secondListBackup.Remove(secondListBackup.Where(v => v == val2).FirstOrDefault());
}
}
}
foreach (int val in firstListBackup)
{
pairs.Add(new Tuple<int?, int?>(val, null));
}
foreach (int val in secondListBackup)
{
pairs.Add(new Tuple<int?, int?>(null, val));
}
return pairs;
}
CodePudding user response：
This is solvable in O(nlog(n)) and O(n).
O(nlog(n))
Sort both lists. This way, you can then linearly traverse both lists checking if an element exists in both lists or not. Some pseudo-code (since I'm not fluent in C# and do not how std::tuple<> works in C ):
firstList.sort();
secondList.sort();
int firstIndex = 0, secondIndex = 0;
int firstSize = firstList.size(), secondSize = secondList.size();
List<Tuple<int?, int?>> output;
while (firstIndex < firstSize && secondIndex < secondSize) {
if (firstList[firstIndex] < secondList[secondIndex]) {
output.Add(firstList[firstIndex], null);
firstIndex ;
continue;
}
if (firstList[firstIndex] > secondList[secondIndex]) {
output.Add(null, secondList[secondIndex]);
secondIndex ;
continue;
}
output.Add(firstList[firstIndex], secondList[secondIndex]);
firstIndex ;
secondIndex ;
}
// Now we just need to "empty" the other, potentially non-empty list.
while (firstIndex < firstSize) {
output.Add(firstList[firstIndex ], null);
}
while (secondIndex < secondSize) {
output.Add(null, secondList[secondIndex ]);
}
This works because every time you can instantly tell if a matching element exists in the "other" list. Simply iterate over the lists in an ascending manner, increasing either index when appropriate.
Potential problem: List may not be easy to sort, but you can linearly convert it to an array.
Also, sorting itself in this case can be done linearly via radix sort, but that's not a very elementary method. Nonetheless, this solution could technically be O(n).
O(n)
This solution involves a HashMap (it has this name in Java, in C it's called an unordered_map, I don't know what it's called in C#). Hashmaps provide constant-time access to keys.
First, convert both lists into hashmaps of numbers of occurences of each value. For instance, for input
[2, 2, 3], [1, 2]
you'd receive the following hasmaps
{(2, 2), (3, 1)}, {(1, 1), (2, 1)}
Then, iterate over the keys of one hashmap checking whether they exist in the other hashmap. If so, add them to the output list in the form (a,a), removing a from both hasmaps. Otherwise, add (a,null). Then, the second hashmap might not be empty so you have to iterate over the remaining elements of the other hashmap to add the elements of the form (null,a) to your output.
In this example, you'd first "see" the key 2 in the first hashmap, with a value of 2, meaning it occurred twice in the first list. The key 2 occurs with value 1 in the second hashmap, so you add (2, 2) to the output, and then add (2, null) to your output. Now, the hashmaps need to be modified to look like this:
{(3, 1)}, {(1, 1)}
Now you "see" element 3 in the first hashmap, so you add (3, null) into the output, because 3 does not occur in the second hashmap.
Lastly, you will notice that the second hashmap has a leftover element and so you add (null, 1) to your output.
CodePudding user response：
Your logic can be achieved in the LINQ way.
listOneleft joinlistTwoby number. Mae sure to convertlistTwoasList<int?>first. This returns the result with bothaandbhave value orahas value.Result from 1 merge (vertially) with
listTwofor thoselistTwo's values don't exist in the result from 1.
public static List<Tuple<int?, int?>> AddPairs(List<int> listOne, List<int> listTwo)
{
var result = (from a in listOne
join b in listTwo.Select(x => (int?)x) on a equals b into ab
from b in ab.DefaultIfEmpty()
select Tuple.Create<int?, int?>(a,b)
).ToList();
return result
.Concat(listTwo.Where(x => !result.Any(y => y.Item1 == x))
.Select(x => Tuple.Create<int?, int?>(null,x)))
.ToList();
}
CodePudding user response：
internal static List<Tuple<int?, int?>> PairInts(List<int> firstList, List<int> secondList)
{
var pairs = new List<Tuple<int?, int?>>();
foreach (var firstItem in firstList)
{
var removedAnyItems = secondList.Remove(firstItem); // Try to remove any corresponding items
pairs.Add(new Tuple<int?, int?>(firstItem, removedAnyItems ? firstItem : null)); // If removed, it will be (a, a). If it cannot be removed, it will be (a, null)
}
foreach (var secondItem in secondList) // Since we removed any corresponding items, this list will not have any corresponding item in first list. So it will be always (null, a)
{
pairs.Add(new Tuple<int?, int?>(null, secondItem));
}
return pairs;
}
CodePudding user response：
You can use this method using LinQ namespace that is optimized.
public static List<(int?, int?)> GetPairs(List<int> list1, List<int> list2)
{
var pairs = new List<(int?, int?)>();
var firstNullableList = list1.ConvertAll(x => (int?)x);
var secondNullableList = list2.ConvertAll(x => (int?)x);
pairs = firstNullableList.ConvertAll(x => (x, secondNullableList.Find(y => y == x)));
pairs.AddRange(secondNullableList.ConvertAll(x => (firstNullableList.Find(y => y == x), x)).Where(x => !pairs.Contains(x)));
return pairs;
}