Найти наименьшую длину последовательности из списка массивов, которые должны содержать элемент из каждого массива

Question

Вот проблема:

Предположим, мы имеем следующие массивы:

[1,2,9] 
[3,6,7] 
[4,11] 
[8,10,12] 

Элементы массива являются уникальными и упорядочены. Задача состоит в том, чтобы найти кратчайшую длину последовательности, которая будет содержать по крайней мере один элемент каждого массива, но эти элементы должны идти один за другим (без пробелов, не может быть [1,3]), а также упорядочены. Поэтому в этом случае ответ будет следующим:

5 => [7,8,9,10,11] 

Есть ли эффективный способ для этого?

Answer 1

Это можно легко решить, как показано ниже.

1. Элемент списка
2. инициализации smallest_range, как MAX_INT
3. держать 3 указатели/индекс p1, p2 и p3, который указывает на первые элементы списков L1, L2 и L3 соответственно.
4. найти максимальное значение и минимальное значение, указанное/проиндексированное p1, p2 и p3
5. Разность максимального значения и минимального значения, обнаруженного на шаге 3, является текущим диапазоном. сравните его с smallest_range и обновите его, если найдете меньше.
6. Приращение указателя/индекс минимального значения, найденного в действии 3.
7. Повторите шаги с 3 по 5, пока указатель/индекс значения min находится в диапазоне.

Alse check this обсуждение. Речь идет о вашей проблеме. Здесь вы также можете найти коды C++ и java

Answer 2

Вы можете использовать алгоритм с двумя указателями (извините, что я не нашел ссылки). Сложность O(nlogn), n - сумма элементов во всех массивах.

Сначала поместите все элементы в 1d-массив, пожертвовав каждый с индексом массива. Так же, как это,

struct A{ 
    int value; 
    int array_id; 
}; 

Тогда, сортировать элементы по значению (O(nlogn)). Наша проблема меняется, чтобы найти кратчайшую непрерывную последовательность, которая охватывает все массивы. Это можно сделать с помощью двух указателей. Сложность составляет O(n).

Таким образом, полная сложность O(nlogn).