代码之家 › 专栏 › 技术社区 › Novice

使用C将整数集转换为范围#

algorithm c#

Novice · 技术社区 · 14 年前

将一组整数转换为一组范围的最常用方法是什么?

例如,给定集合{0,1,2,3,4,7,8,9,11}我想用C得到{0,4},{7,9},{11,11}#

这个问题已经用C++回答了 Solution in C++

3 回复 | 直到 8 年前

Alastair Maw 14 年前

这不是很有效,但是是惯用的:

var nums = new HashSet<int>{0, 1, 2, 3, 4, 7, 8, 9, 11};
IEnumerable<Tuple<int, int>> ranges = Enumerable.Zip(
    nums.Where(n => !nums.Contains(n - 1)),
    nums.Where(n => !nums.Contains(n + 1)),
    Tuple.Create);

更有效,假设它被排序:

public IEnumerable<Tuple<int, int>> GetContiguousRanges(IEnumerable<int> nums)
{
    int start = nums.First();
    int last = start - 1;
    foreach (int i in nums)
    {
        if (i != last + 1)
        {
            yield return Tuple.Create(start, last);
            start = i;
        }
        last = i;
    }
    yield return Tuple.Create(start, last);
}

luqui 14 年前

这应该是一个相当直接的音译从你提到的帖子。确保将此代码放在某个类中,C代码必须在某个类中。我假设你对C不太熟悉,所以我会尽我所能展示出它们的相同点和不同点,希望你能处理好其余的问题。

struct Range
{
    public Range (int start, int end) { this.start = start; this.end = end; }
    public int start;
    public int end;
}

public static void SetToRanges(Dictionary<int,bool> indices, List<Range> ranges) 
{
    Range r = new Range(int.MinValue, int.MaxValue);
    foreach (int i in indices.Keys)
    {
        // translate rest of code here
    }
    ranges.Add(r);
    return ranges;
}

为了得到更地道的独白,我将返回一个 IEnumerable<Range> ,因此“list”可以同时构建和迭代:

public static IEnumerable<Range> SetToRanges(Dictionary<int, bool> indices)
{
     // instead of "ranges.Add(r)", use "yield return r".
     // This returns multiple values in order from the function, that can
     // be iterated with "foreach (Range i in SetToRanges(foo))"
}