Вопрос:

Получить фрагменты массива в порядке длины

c# .net

83 просмотра

3 ответа

543 Репутация автора

У меня есть следующий код, чтобы получить список всех возможных индексов начала / конца слайса, в порядке убывания длины слайса. Затем я перебираю список и использую его для разбиения массива, разрывая его, когда получаю искомый фрагмент. Я делаю это, потому что я ищу самый большой срез, который соответствует другим параметрам, и я ищу кратчайший путь мимо других возможных срезов, как только я нашел один.

Я бы предпочел пару вложенных циклов for, чтобы проверить срез и двигаться дальше, вместо того, чтобы сначала получать все возможные диапазоны и сортировать их, поскольку массив может иметь до миллиарда или более элементов. Я не могу понять, как это сделать, или даже как сформулировать вопрос, чтобы найти его. Любая помощь приветствуется.

byte[] data1 = { 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 6, 4 };

List<Tuple<int, int>> ranges = new List<Tuple<int, int>>();
for (int i1 = 0; i1 < data1.Count(); i1++)
{
    for (int i2 = i1 + 1; i2 < data1.Count(); i2++)
    {
        ranges.Add(new Tuple<int, int>(i1, i2));
    }
}


ranges = ranges.OrderByDescending(x => x.Item2 - x.Item1).ToList();
Автор: Broom Источник Размещён: 22.08.2016 09:31

Ответы (3)


1 плюс

8722 Репутация автора

Вы можете перечислить фрагменты напрямую с помощью пары вложенных циклов:

bool found = false;
for (int sliceLen = data1.Length; !found && sliceLen > 0; sliceLen--)
    for (int sliceStart = 0; !found && sliceStart + sliceLen <= data1.Length; sliceStart++)
        if (found = (
            data1[sliceStart] == data1[sliceStart + sliceLen - 1]   // check your condition here
        ))
            Console.WriteLine($"Found: {sliceStart}:{sliceLen}");

Демо: https://ideone.com/lZRNJm

Автор: Dmitry Egorov Размещён: 22.08.2016 09:50

1 плюс

53163 Репутация автора

Решение

Если я правильно понимаю вопрос, вы ищете самый большой подмассив массива (который вы называете «срезом»… может быть, термин из какого-то другого языка программирования?), Который удовлетворяет некоторым конкретным условиям. В вашем вопросе вы не указали сами условия, поэтому я предполагаю, что эта часть не важна.

Кажется, что у вас есть трудности с организацией вашего кода, так что вы сначала обязательно проверяете самые длинные подмассивы.

Если все это правильно, то вам просто нужно расположить петли по-другому. В настоящее время вы выбираете начальный индекс, а затем находите все подмассивы, начинающиеся с этого индекса. Вместо этого, поскольку вы хотите, чтобы самые длинные подмассивы проверялись первыми, вы должны выбрать длину подмассива, начиная с самой длинной возможной длины, и выбрать все подмассивы, которые могут быть этой длины.

Например:

for (int i = data1.Length; i > 0; i--)
{
    for (int j = 0; j < data1.Length - i + 1; j++)
    {
        // inspect subarray starting at index j, having length i
    }
}
Автор: Peter Duniho Размещён: 22.08.2016 09:51

0 плюса

543 Репутация автора

Я понял. Вот что мне нужно, чтобы перебрать каждый фрагмент массива в обратном порядке длины.

byte[] data1 = { 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 6, 4 };


for (int length = data1.Count() - 1; length > 0; length--)
{
    int numberOfSlicesForLength = data1.Count() - length;

    for (int start = 0; start < numberOfSlicesForLength; start++)
    {
        byte[] sliceValues = data1.Skip(start).Take(length);
    }
}
Автор: Broom Размещён: 23.08.2016 02:18
32x32