Как эффективно определить максимальное значение ниже порога?

Question

У меня есть два списка.Список L1 содержит все положительные целые числа, список L2 содержит положительные числа (e.g. 0.01,0.1,0.5,3,5,10,100....).

Учитывая небольшое положительное число M (e.g. 0.10948472), найдите a,b из L1 и c из L2 st (b/a)*c развернуто, но все еще <=M

Обратите внимание, что список L2 фиксирован (длина около 7000), список L1 имеет переменную длину (может иметь один элемент или до3000 элементов).

Как мы можем эффективно разработать алгоритм для решения этой проблемы?Я думаю об использовании разделяй и властвуй в списке L1, чтобы разбить его на две части, а затем объединить, но это не сработало.Кто-нибудь может решить это эффективно?

Обновление: в настоящее время я разработал несколько неэффективных, но правильных решений: сначала отсортируйте «L1».Разделите 'L1' на два блока: один блок - это первые N-1 элементы, другой блок - последний элемент.Предположим, что лучшее a,b,c было найдено в первых N-1 элементах L1, я проверяю, можем ли мы найти a в первом блоке и b во втором блоке (только один элемент) и некоторые c, такой, что (b/a)*c улучшается.Так как я должен пройти через каждый элемент в L2, хотя это nlogn, он все еще выглядит медленно

Answer 1

из того, что я понимаю, вам не нужно проходить через каждый элемент L2 для данной комбинации a / b.Сортировка L2 в порядке возрастания.затем предположим, что вы выбрали первую комбинацию a / b из L1.для c вы можете выбрать элемент в середине L2, то есть с индексом 3500 и умножить на a / b.если ответ меньше, чем M, вы можете выбрать элемент с более высоким индексом, например, при 7000 * 3/4, который равен 5250. Если ответ еще меньше, идите еще выше.если вместо этого (a / b) * c превышает M, выберите более низкий индекс.Вы можете сходиться к максимальному значению c для этой конкретной комбинации a / b.

PS Излишне говорить, что после сортировки L1 и L2 можно добавить оператор if, чтобы исключить те элементы в L1 или L2, которые всегда будут превышать M для любого значения L2 или L1 соответственно.

Answer 2

Сортировка L1 по возрастанию.Допустим, | L1 |= п.Это O (n log n).

Для каждого элемента в L2 ('c' в уравнении) выполните следующие действия (т. Е. O (1) раз, поскольку L2 зафиксировано).

1. For the first element in L1 (which we'll treat as the 'a' in the equation), use binary search on L1 to find a second element (the 'b') s.t. (b/a)*c is maximized but still <=M.
2. Now, we'll move on to the next element in L1. Note that we're increasing the denominator, so the numerator will either stay the same or increase. We'll just iterate rather than using binary search.
3. repeat step 2.

В шагах 2 и3 мы отслеживаем лучшие значения, которые мы до сих пор нашли для a, b и c.

Время выполнения: O (n log n) для сортировки, затем на шаге 2 мы только увеличиваем числительили знаменатель один раз от каждого значения, так что это O (n) + O (n) = O (n).

Это использует преимущество фиксации L2.Если | L2 | = m и m не зафиксировано, то для этого потребуется O (n log n) + O (m * n)

Answer 3

Эта проблема 3SUM-hard , поэтому вы вряд ли добьетесь значительно большего успеха, чем Theta (n ^ 2).Если я правильно понимаю, ваш текущий алгоритм O (n ^ 2 log n), который не оставляет много места для улучшения.