Reputation: 901
Is it possible for me to use LINQ in a way that allows me to determine that "9" is the first missing value in the sorted list without using a for-loop and comparing each value to the one adjacent to it?
var listStringVals = new [] { "7", "13", "8", "12", "10", "11", "14" };
// sort list to "7","8","10","11","12","13","14"
var sortedList = listStringVals.OrderBy(c => int.Parse(c)).ToList();
// need some magic here to get the first gap in the sorted list
Upvotes: 27
Views: 15215
Reputation: 3355
Why not just use All
since all of the members in the collection need to conform to the criteria...
Example
someVar.All(v => someVar.Contains(v + 1) || v == someVar.Last())
Then you don't have to order and its nicer.
You could sort after this step or even during if you needed to but I personally would just use the sorted collection and have it do that work for me.
You would grab the values if you needed to after doing the check then return the result of the check or hide it if you wanted to for some reason via a multi-line modification above along with a list to store the values in.
e.g.
someVar.All((v) => {
bool result = someVar.Contains(v + 1) || v == someVar.Last();
if(!result) someList.Add(v);
return true;
});
Checking the count of the list (which could be ordered) for a non zero value to indicate if it satisfied or not.
Upvotes: 1
Reputation: 25014
var listStringVals = new string[] {"7", "13", "8", "12", "10", "11", "14"};
var sortedInts = listStringVals.Select(c => int.Parse(c)).OrderBy(x => x);
var noGaps = Enumerable.Range(sortedInts.First(),
sortedInts.Last() - sortedInts.First() + 1);
var missing = noGaps.Except(sortedInts).Select(x => x.ToString()).First();
Edit: fixed range generation thanks to BeemerGuy's answer. Still leaving mine, as it doesn't ignore the ugliness of a list of string
representations of int
s :)
Upvotes: 5
Reputation: 22565
It's a little late but I think it's a cool way of doing this:
List<int> listStringVals = (new int[] { 7, 13, 8, 12, 10, 11, 14 }).ToList();
listStringVals.Sort();
return listStringVals.Skip(1).Select((x, i) => x - listStringVals[i] == 1).Any(x => !x);
Upvotes: 1
Reputation: 100308
Let
var strings = new string[] { "7", "13", "8", "12", "10", "11", "14" };
Then
var list = Array.ConvertAll(strings, s => Int32.Parse(s)).OrderBy(i => i);
// or
var list = strings.Select(s => int.Parse(s)).OrderBy(i => i);
// or
var list = strings.OrderBy(s => int.Parse(s));
(note this question)
and then
var result = Enumerable.Range(list.Min(), list.Count).Except(list).First(); // 9
// or
int min = list.Min(), max = list.Max();
var result = Enumerable.Range(min, max - min + 1).Except(list).First();
Upvotes: 64
Reputation: 144176
string firstGap = sortedList
.Zip(sortedList.Skip(1), (f, s) => Tuple.Create(f, s))
.First(tup => (int.Parse(tup.Item1) + 1) != int.Parse(tup.Item2)).Item1;
Should give you the first item before the first gap, so the first missing element is:
string gap = (int.Parse(firstGap) + 1).ToString();
Upvotes: 3
Reputation: 169143
(abatishchev beat me to the punch, but his answer is better anyway. However, since alternate solutions to the same problem can be fun, I am still posting this.)
Hackity hack hack. But working, if you really want to do this. Performance will be awful, because this technique will not stop when it finds the answer -- it will always loop over every number! But it will work:
public static int FindFirstMissing(IEnumerable<int> sequence)
{
bool found = false;
int agg = sequence.Aggregate((aggregate, next) => {
if (found)
return aggregate;
if (next - aggregate != 1) {
found = true;
return aggregate + 1;
}
return next;
});
if (!found)
throw new ArgumentException("sequence", "Contains no missing numbers.");
return agg;
}
Upvotes: 3
Reputation: 8269
Here's a way to get you started (I used int
values here):
List<int> listStringVals = (new int[] { 7, 13, 8, 12, 10, 11, 14 }).ToList();
List<int> SortedList = listStringVals.OrderBy(c => c).ToList();
List<int> Gaps = Enumerable.Range(SortedList.First(),
SortedList.Last() - SortedList.First() + 1)
.Except(SortedList).ToList();
Upvotes: 17