Самый короткий подсписок, включающий элемент N с общим> MIN - PullRequest
Новая
       7

Самый короткий подсписок, включающий элемент N с общим> MIN

1 голос
/ 04 марта 2011

Пример:

Дан список случайных чисел [1,5,1,1,3,10,5,4,2,1], тестовый элемент N=10 at index 5 и MIN=20.

Самый короткий подсписок, включающий 10 с total>20, - это, очевидно, список [3,10,5,4] с total=22 и size=4.

Проблема:

Что такое алгоритм для эффективного поиска такого подсписка?

Edit:

  1. Могут быть разные подсписки, которые удовлетворяют условию "самый короткий". [10,5,4,2] так же короток, как [3,10,5,4], и допустимый результат тоже.

  2. «Подсписок» в этом вопросе является последовательным блоком пунктов исходного списка. [5,10,5,4] не является допустимым подсписком (я бы назвал его подмножеством).

Ответы [ 2 ]

1 голос
/ 04 марта 2011

Следующий алгоритм должен быть O (n):

Начиная с тестового элемента, идти добавлять элементы влево до суммирования> = min.Это дает первое предположение о длине подсписка l (начиная с индекса i).Не увеличивайте начальный индекс i подсписка длины l с каждым шагом (пока вы не достигнете своего тестового элемента) и с каждым шаговым тестом, если вы можете сократить подсписок на один (справа, то есть уменьшить длину l), не становясь меньше min.

Позаботьтесь о крайних случаях: сумма слева недостаточно велика или общая сумма недостаточно велика.

0 голосов
/ 08 марта 2011

Нахождение кратчайшего подсписка> MAX - это то же самое, что нахождение кратчайшего подсписка <= MAX, где сумма подсписка превышает MAX, если добавлен элемент до или после: С <code>[1,5,1,1,3,10,5,4,2,1] и MAX=20, [1,3,10] это подсписок, включающий 10, но недействительный, поскольку добавление следующего 5 дает в сумме 19 < MAX. Первый действительный подсписок здесь [5,1,1,3,10].

Алгоритм:

  1. Создайте marker для длины самого короткого найденного подсписка.
  2. Создание курсоров left и right.
  3. Установите оба курсора на N.
  4. Переместить left влево while total(at left, ..., at N) <= MAX или left = 0.
    1. Если left > 0, хранить n - left + 1 в marker. Перейти к 6.
  5. Переместить right вправо while total(at left, ..., at right) <= MAX или right = list.size - 1.
    1. Если right < list.size - 1 сохранить right - left + 1 в marker.
    2. Остальное: возврат list.size.
  6. Петля while left < N and right < list.size - 1:
    1. Переместите left по одному вправо.
    2. Проверьте предмет at right + 1, если есть.
      1. Если total + at right + 1 > MAX хранить right - left + 1 в marker.
      2. В противном случае двигайтесь вправо на один вправо.

В любом случае, я дам ответ Говарду.

...