Нужно найти самые низкие различия между первой строке массива и остальных из них

Question

Ну, я был дан ряд пар элементов (s,h), где s Посылает h элемент на s -м ряду 2D-массива. Не обязательно, чтобы каждая строка имела одинаковое количество элементов, только известно, что не может быть больше N элементов на линии.

Что я хочу сделать, это найти самую низкую самую большую разницу (!) Между определенным элементом первой строки и остальными.

Таким образом, если у меня есть 3 строки с (101,92) (100,25,95,52,101) (93,108,0,65,200), то я хочу найти 3, потому что мне нужно выбрать 92, и у меня 95-92 = 3 от первого до второго и 93-92 = 1 от первой до третьей.

Я достиг точки, когда он уверен, что если у меня есть s линии с n(i) элементов каждый и i=0..s, затем n0<=n1<=...<=ns так, чтобы иметь хороший средний сценарий производительности при выборе наилучшего соответствия с 1-й линии по отношению к другим.

Тем не менее, я не могу придумать способ ниже, чем O (п), или даже может быть, О (п) в некоторых случаях. Кто-нибудь имеет предложение об улучшенном способе сделать это?

Answer 1

Объедините все строки в один список, также отслеживая, какой элемент происходит от того места.

Сортировка этого списка.

Имейте переменную последнего значения для каждой строки.

Для каждого элемента в отсортированном списке обновите переменную последнего значения применимого списка. Если не все строки имеют значение последнего значения, ничего не делайте. Если это элемент из первого списка:

• Пересчитайте большую разницу для всех переменных последнего значения. Храните эту разницу.

Если это элемент из любого другого списка:

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

Наименьшая разница - это желаемое значение.

Пример:

Lists: (101,92) (100,25,95,52,101) (93,108,0,65,200) 

Sorted 0 25 52 65 92 93 95 100 101 101 108 200 
Source 2 1 1 2 0 2 1 1 0 1 2 2 

Last[0] - - - - 92 92 92 92 101 101 101 101 
Last[1] - 25 52 52 52 52 95 100 100 101 101 101 
Last[2] 0 0 0 65 65 93 93 93 93 93 108 200 

Diff - - - - 40 41 3 8 8 8 7 9 
Best - - - - 40 40 3 3 3 3 3 3 

Лучший = 3, как требуется. Хранение фактических предметов или их обнаружение впоследствии должно быть достаточно простым.

Сложность:

Пусть n будет общее количество элементов и k быть количество списков.

O(n log n) для комбайна + сортировать.

O(nk) (в наихудшем случае) для сканирования, поскольку мы проверяем n элементов и, при каждом товаре, делаем максимум O(k) работы.

So O(n log n + nk).