将1、2、3、4、5、6、8、10、11显示为1-6、8、10-11。

Question

我有这个序列 1,2,3,4,5,6,8,10,11 期望输出为 1-6,8,10-11 这个问题是关于将序列格式化为易读形式的。

我尝试使用C＃并使用了许多if和else。

面试官说，有一些简单的算法可以解决这个问题。

我不知道如何实现这个非常简单的算法。

同时，对于1,2,3，我展示了1-3。他们说这是错误的！

这个逻辑中涉及到任何设计模式（解释器）吗？

- Billa

---

他们说转换从1,2,3到1-3为什么是错误的？我看不出这种情况有什么问题。 - Jarek

可能是 java display input in range 的重复问题。 - Ivaylo Strandjev

是啊，我只是在想1-3是错的，因为你应该输出1-4，还是说它是错的，因为他们只想要替换一行中的4个或更多元素，而不是3个元素。 - Rawling

我喜欢这个问题有九个带代码的答案，但没有一个解释性的答案。（是的，这是一个相当简单的算法；但仍然如此。） - Konrad Rudolph

@KonradRudolph: 如果您认为有必要，可以自由添加一个。 - Daniel Hilgarth

Answer 1

这是一种实现方法：

        int[] numbers = { 1, 2, 3, 4, 5, 6, 8, 10, 11 };

        int start, end;
        for (int i = 0; i < numbers.Length; i++)
        {
            start = numbers[i];

            while (i < numbers.Length - 1 && numbers[i] + 1 == numbers[i + 1])
                i++;

            end = numbers[i];

            if(start == end)
                Console.WriteLine(start);
            else
                Console.WriteLine(start + " - " + end);
        }

这将显示随着范围增加而递增的后续数字。不是线性递增的数字不作为范围的一部分写入。

以下是第一种方法的另一个版本，它利用相同的 for 循环来迭代范围：

        int temp = numbers[0], start, end;
        for (int i = 0; i < numbers.Length; i++)
        {
            start = temp;

            if (i < numbers.Length - 1 )
                // if subsequent numbers are incremental loop further
                if (numbers[i] + 1 == numbers[i + 1])
                    continue;
                // if they are not, number at index i + 1 is a new 'start' for the next iteration
                else
                    temp = numbers[i + 1];

            end = numbers[i];

            if (start == end)
                Console.WriteLine(start);
            else
                Console.WriteLine(start + " - " + end);
        }

- Ivan Golović

---

这个逻辑我觉得很简单 :) - Billa

我同意，逻辑和实现都相当简单 :) - Ivan Golović

@IvanG 反过来是否也可能呢？如果用户输入为10,1-4,5-8,9，则输出应为1,2,3,4,5,6,7,8,9,10。 - Xavier

Answer 2

一个简单的C#实现可能如下所示：

public string Format(IEnumerable<int> input)
{
    var result = string.Empty;

    var previous = -1;
    var start = -1;
    var first = true;

    foreach(var i in input)
    {
        if(start == -1)
            start = i;
        else if(previous + 1 != i)
        {
            result += FormatRange(start, previous, first);
            first = false;
            start = i;
        }

        previous = i;
    }

    if(start != -1)
        result += FormatRange(start, previous, first);

    return result;
}

public string FormatRange(int start, int end, bool isFirst)
{
    var result = string.Empty;
    if(!isFirst)
        result += ", ";
    if(start == end)
        result += start;
    else
        result += string.Format("{0}-{1}", start, end);
    return result;
}

这也会输出1-3，对于输入的1,2,3来说是完全有效的。如果没有规定输出应该是什么，那么回答这部分是不可能的。

- Daniel Hilgarth

---

不错的回答，但我认为（至少是面试问题的）重点是找到一个简单的算法，而不是通过使用API来“作弊”。 - Bernhard Barker

@Dukeling：识别范围使用简单算法完成。 - Daniel Hilgarth

@Dukeling：但是我还是改了它，不使用LINQ输出。 - Daniel Hilgarth

Answer 3

这可能不是一个适合面试问题的回答，但使用LINQ也是解决这个问题的另一种方式。

int[] numbers = { 1, 2, 3, 4, 5, 6, 8, 10, 11 };
var remains = numbers.AsEnumerable();

while (remains.Any())
{
    int first = remains.First();
    int last = remains.TakeWhile((x, i) => x - first == i).Last();
    remains = remains.Skip(last - first + 1);
    Console.Write(first + (first == last ? "" : "-" + last) + (remains.Any() ? "," : Environment.NewLine));
}

- Fung

---

这是最整洁的版本。 - Adrian Marinica

请注意，这会对源序列进行多次迭代，这对于任意可枚举对象来说都不适用，即使它对数组有效。 - Servy

Answer 4

Java代码：

int[] arr = {1,2,3,4,5,6,8,10,11};
int start = arr[0], last = arr[0];
String output = "";

for (int i = 1; i <= arr.length; i++)
{
  if (i == arr.length || arr[i] != last+1)
  {
    if (output.length() != 0)
      output += ",";
    if (start == last)
      output += start;
    else
      output += start + "-" + last;
    if (i != arr.length)
      start = last = arr[i];
  }
  else
     last = arr[i];
}

System.out.println(output);

- Bernhard Barker

Answer 5

这是我的最佳尝试。虽然不太聪明，但我认为足够简单，以满足要求。但我仍然很困惑为什么“1-3”是错误的....

    var numbers = new int[] { 1, 2, 3, 4, 5, 6, 8, 10, 11, 12 };

    var groups = new Dictionary<int, int>();
    groups.Add(numbers.First(), numbers.First());

    foreach (var num in numbers.Skip(1))
    {
        var grp = groups.Last();
        if (grp.Value + 1 == num)
        {
            groups[grp.Key] = num;
        }
        else
        {
            groups.Add(num, num);
        }
    }

    var output = string.Join(",", groups.Select(grp => (grp.Key == grp.Value) ? grp.Value.ToString() : grp.Key.ToString() + "-" + grp.Value.ToString()));

注意：当然，使用字典和linq等是完全不必要的（并且对于需要算法的答案来说太具体了），但我认为它很好地突出了问题的分组方面。

- Kevin Versfeld

Answer 6

以下内容将一组连续整数分组，并为每个组输出一个字符串。但是，它还允许您指定要连字符化的最小组长度；任何长度小于此值的组都只会给您单独的数字。因此，如果您只想连字符化4个或更多的组，可以传入4；如果您想连字符化成对的数字，可以传入2。（我自己想使用3，但我无法确定他们想要什么。）

它在进行操作时也不会保留任何数字集合，因为您不需要这样做。

方法：

static IEnumerable<string> Group(IEnumerable<int> input, int minLength)
{
    int currentStart = int.MinValue;
    int currentLength = 0;
    foreach (int c in input)
    {
        if (currentLength > 0)
            if (currentStart + currentLength == c)
                currentLength++;
            else
            {
                if (currentLength >= minLength)
                    yield return string.Format("{0}-{1}",
                        currentStart, currentStart + currentLength - 1);
                else
                    for (int i = currentStart; i < currentStart + currentLength; i++)
                        yield return i.ToString();
                currentStart = c;
                currentLength = 1;
            }
        else
        {
            currentStart = c;
            currentLength = 1;
        }
    }
    if (currentLength >= minLength)
        yield return string.Format("{0}-{1}",
            currentStart, currentStart + currentLength + 1);
    else
        for (int i = currentStart; i < currentStart + currentLength; i++)
            yield return i.ToString();
}

使用方法：

int minCount = 3;
int[] input = new[] { 1, 2, 3, 4, 5, 6, 8, 10, 11 };
Console.WriteLine(String.Join(",", Group(input, minCount)));

- Rawling

Answer 7

这不是有效的C#代码，只是为了展示思路。

将列表从最小值排序到最大值，然后执行以下操作：

For i = Min to Max
{
  if i < MaxFound
    continue;

  int step = 1;
  Output = i;
  while Found(i + Step)
  {
     Step++;
     MaxFound = i + Step;
  }
  if i < MaxFound 
    Output = (i + "-" + MaxFound);

  Output += ", ";
}

- CloudyMarble

Answer 8

这是一个方法之一：

public static void main(String[] args) {
    print(1, 2, 3, 4, 5, 7, 9, 10, 12);
}

public static void print(int ... nums) {
    System.out.print(nums[0]);
    int idx = 1;

    for(int i = 1; i < nums.length; i++, idx++) {
        if(nums[i] - nums[i - 1] != 1) {
            if(idx > 1) {
                System.out.print(" - " + nums[i - 1]);
            }
            System.out.print(", " + nums[i]);
            idx = 0;
        }
    }

    if(idx > 1)
        System.out.println(" - " + nums[nums.length - 1]);
}

- Shivam

---

我看不到格式中的第一个数字。它显示为-5而不是1-5。 - Billa

@BadDeveloper 第一行代码打印了第一个元素。也许你错过了它！ - Shivam

Answer 9

这是一个 Haskell 版本：

import Data.List

parseRange [] = ""
parseRange n = 
  let range = takeWhile (\x -> isInfixOf [x,x+1] n) n
  in if not (null range)
        then show (head range) ++ "-" ++ show (last range + 1) 
             ++ (if length (tail n) > 1 then "," else "") 
             ++ parseRange (drop (length range + 1) n) 
        else show (head n) ++ (if null (tail n) then "" else ",") 
             ++ parseRange (drop 1 n)

输出：

*Main> parseRange [1,2,3,4,5,6,8,10,11]
"1-6,8,10-11"

- גלעד ברקן

Answer 10

还有一种使用 F# 中 fold 实现的方法 - 只是为了好玩。

let parseRange numbers = 
  numbers 
  |> Seq.fold 
    (fun list n -> 
      match list with
      |(a,b) :: tail when b+1 = n -> (a, n) :: tail
      |_ -> (n,n) :: list) []
  |> List.rev 
  |> Seq.map (fun (a,b) -> if a = b then sprintf "%i" a else sprintf "%i-%i" a b)
  |> String.concat ","

- Yodiz