April 29, 2021
Here is the link.
C# | greedy algorithm | Two hashmaps to track records | Case study
April 29, 2021
Introduction
I quickly reviewed my own C# code written in 2019, and then made a few changes to speed up the code.
Case study
var values = new int[] { 5, 4, 3, 2, 1 };
var labels = new int[] { 1, 3, 3, 3, 2 };
var result = LargestValsFromLabels(values, labels, 3, 2);
Debug.Assert(result == 12);
The question is to ask what is maximum value to find, three numbers, total number of values with same label should not exceed 2. The answer is 12, which is sum of 5 + 4 + 3. The greedy algorithm is applied to find largest value first, and then continue to try to add next smaller one if label count constraint is not broken. The detail is written in the following.
The idea is to put values into C# Dictionary object, a hashmap variable called "map", so values = {5, 4, 3, 2, 1} will be saved into hashmap, for example, first value is 5, label is 1, so map[5] = 1. All values are saved in the following:
map[5] = 1, map[4] = 3, map[3] = 3, map[2] = 3, map[1] = 2.
Next step is to get all keys from hashmap map, and put into an array. Sort the array in descending order. Apply greedy algorithm, go over largest key first, and then choose it into the set if it's label count is still available.
The extra work is to use a hashmap called "used" to track how many numbers are chosed based on label value.
The biggest key is 5, so it is chosen. used hashmap used[5] =1; next biggest key is 4, and 4 is chosen, since value 4's label is 3, so used[3] = 1. Next biggest key is 3, and 3's label is 3, and used[3] = 1 < 2, so 3 can be added to largest value set. All three values are found with sum = 5 + 4 + 3 = 12.
Test case
values = [3,2,3,2,1]
labels = [1,0,2,2,1]
The number in values array may not be unique, so in other words, one number may have different labels. The above test case, the first and third number both are 3, but labels are different. One is 1, second one is 2. In my design, C# variable name map is defined using Dictionary<int, List>, not Dictionary<int, int>.
Simplicity
Avoid using C# SortedDictionary, since keys only needs to be sorted once after all are saved. No need to maintain a SortedDictionary data structure.
The following code was modified based on my previous practice here. The following code passes online judge.
public class Solution {
static void Main(string[] args)
{
RunTestcase2();
}
public static void RunTestcase1()
{
var values = new int[] { 5, 4, 3, 2, 1 };
var labels = new int[] { 1, 1, 2, 2, 3 };
var result = LargestValsFromLabels(values, labels, 3, 1);
Debug.Assert(result == 9);
}
public static void RunTestcase2()
{
var values = new int[] { 5, 4, 3, 2, 1 };
var labels = new int[] { 1, 3, 3, 3, 2 };
var result = LargestValsFromLabels(values, labels, 3, 2);
Debug.Assert(result == 12);
}
public int LargestValsFromLabels(int[] values, int[] labels, int num_wanted, int use_limit)
{
var map = new Dictionary<int, List<int>>();
var length = values.Length;
for (int i = 0; i < length; i++)
{
var key = values[i];
var value = labels[i];
if (!map.ContainsKey(key))
{
map.Add(key, new List<int>());
}
map[key].Add(value);
}
var usedCount = new Dictionary<int, int>();
var numbers = map.Keys.ToArray();
Array.Sort(numbers);
int index = 0;
length = numbers.Length;
var sum = 0;
for (int i = length - 1; i >= 0; i--)
{
var key = numbers[i];
var list = map[key];
foreach (var item in list)
{
if (!usedCount.ContainsKey(item))
{
usedCount.Add(item, 0);
}
if (usedCount[item] < use_limit)
{
index++;
sum += key;
usedCount[item]++;
if (index == num_wanted)
{
return sum;
}
}
}
}
return sum;
}
}