c4melot
BAN USER{
class Program
{
static void Main(string[] args)
{
var generator = new LowestNumberGenerator();
string result1 = generator.Generate("4205123", 4);
string result2 = generator.Generate("216504", 3);
}
}
public class LowestNumberGenerator
{
public string Generate(string number, int n)
{
var digitsMap = new SortedDictionary<int, SortedSet<int>>();
for (int i = 0; i < number.Length; i++)
{
char c = number[i];
var digit = (int)char.GetNumericValue(c);
if (digitsMap.ContainsKey(digit))
{
var sortedList = digitsMap[digit];
sortedList.Add(i);
}
else
{
var sortedSet = new SortedSet<int>();
sortedSet.Add(i);
digitsMap.Add(digit, sortedSet);
}
}
int targetCount = number.Length - n;
foreach (KeyValuePair<int, SortedSet<int>> uniqueDigits in digitsMap)
{
int currentDigitMinIndex = uniqueDigits.Value.Min;
var resultSet = new SortedSet<int>();
foreach (KeyValuePair<int, SortedSet<int>> digits in digitsMap)
{
var viewBetween = digits.Value.GetViewBetween(currentDigitMinIndex, number.Length);
resultSet.UnionWith(viewBetween);
if (resultSet.Count >= targetCount)
{
break;
}
}
if (resultSet.Count >= targetCount)
{
string result = string.Empty;
foreach (var index in resultSet)
{
result += number[index];
}
return result;
}
}
return string.Empty;
}
}
}
Hello,
Is think that approach to this problem should not be as complex as it sounds.
Generally, I see this problem is a matter of inserting all values from all arrays in Binary Search Tree and performing in-order traversal to add all items in newly allocated array.
Time complexity for this is N log N (to fill binary search tree) and N operations to traverse tree, thus making it O(N log N) operation.
What about redundant conversion code, isn't it a waste of resources to parse string just in order to figure out whether it's parsable?
- c4melot March 15, 2015