3

Есть списки вида:

0 0 0 1 0 1 1 1 1 0 0 2 2 0 1 1 0 0

Необходимо разбить этот список на интервалы, без учета нулей. На выходе массив интервалов состоящий из подряд идущих одинаковых элементов.

Например:

[0] = 1, [1] = 1 1 1 1, [2] = 2 2, [3] = 1 1

Каким образом это лучше сделать?

3
  • А куда делись у вас пустые интервалы? И что должно получиться из последовательности 1 2 3 0 4?
    – VladD
    27 мар 2016 в 8:01
  • Приношу извинения что не рассмотрел все варианты.Пустых интервалов не должно быть, нули опускаются. Из последовательности 1 2 3 0 4, получаются интервалы [0] = 1, [1] = 2, [2] = 3, [3] = 4. Не знаю как в комментариях код оформлять.. Upd: поправил шапку сообщения.
    – Nayils
    27 мар 2016 в 10:10
  • В комментариях код будет нечитаемым, добавьте лучше в вопрос (его можно редактировать).
    – VladD
    27 мар 2016 в 10:34

3 ответа 3

1
  1. Добавим нули к началу и концу списка, чтобы начало и конец были явно ограничены.
  2. Получим индексы позиций, в которых находятся нули.
  3. Получим последовательности, лежащие между нулями.
  4. Вернём все не пустые последовательности.
    Примерно так:

    var baseList=new int[] { 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 2, 2, 0, 1, 1, 0, 0 };
    
    var surrList = new List<int> { 0 };
    surrList.AddRange(baseList);
    surrList.Add(0);
    var zeroindex = surrList.Select((s, i) => new {s, i})
            .Where(x => x.s == 0).Select(x=>x.i).ToArray();
    var result = zeroindex.Select((z, zi) => surrList.ToArray()
            .Where((s, si) =>
                    zi<zeroindex.Length-1 
                    && si>zeroindex[zi] 
                    && si<zeroindex[zi+1]
                  ).ToList())
            .Where(x=>x.Any()).ToList();
    
1
  • Спасибо, очень короткое решение. Но я забыл уточнить, что необходимо, что бы интервалы состояли именно из одинаковых идущих друг за другом элементов. В любом случае огромное спасибо.
    – Nayils
    27 мар 2016 в 11:27
0

Не такое короткое решение, но за O(n) и без добавления дополнительных маркеров.

static void Main(string[] args)
{
    var data = new[] { 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 2, 2, 0, 1, 1, 0, 0 };

    var result = new List<List<int>>();
    var interval = new List<int>();
    int? previousItem = null;

    for (int i = 0; i < data.Length; i++)
    {
        var item = data[i];
        if (item != 0)
        {
            // если число не совпадает с предыдущим, текущий интервал завершен
            if (previousItem.HasValue && previousItem.Value != item)
            {
                result.Add(interval);
                interval = new List<int>();
            }
            previousItem = item;
            interval.Add(item);
        }
        else
        {
            if (interval.Count > 0)
            {
                // если заполняли интервал, то добавляем его в список результатов
                result.Add(interval);
                interval = new List<int>();
                previousItem = null;
            }
            else
            {
                // иначе переходим к следующему элементу
                continue;
            }
        }
    }

    // исходная последовательность обработана, добавляем последний интервал
    if (interval.Count > 0)
    {
        result.Add(interval);
    }

    foreach (var item in result)
    {
        Console.WriteLine(string.Join(" ", item.ToArray()));
    }
}
3
  • Спасибо за ответ. Но я забыл уточнить, что необходимо, что бы интервалы состояли именно из одинаковых идущих друг за другом элементов... (Шапку вопроса поправил)
    – Nayils
    27 мар 2016 в 11:37
  • @Nayils исправил.
    – andreycha
    27 мар 2016 в 12:32
  • @Nayils не за что!
    – andreycha
    27 мар 2016 в 19:26
0

Довольно простой универсальный метод:

public IEnumerable<IEnumerable<T>> GroupConsecutive<T>(IList<T> items, Predicate<T> filter)
{
    for (int i = 0; i < items.Count; i++)
    {
        if (!filter.Invoke(items[i]))
            continue;

        var current = items[i];
        var result = new List<T>();

        while (items[i].Equals(current))
        {
            result.Add(items[i]);
            i++;
        }

        yield return result;
    }
}

Использование:

var input = new int[] { 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 2, 2, 0, 1, 1, 0, 0 };
var output = GroupConsecutive(input, x => (x != 0)); // {{1}, {1, 1, 1, 1}, {2, 2}, {1, 1}}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.