Меня попросили в интервью. Учитывая список целых чисел, как мы можем найти самый большой интервал, который имеет все его члены в данном списке?
например. данный список 1,3,5,7,4,6,10, тогда ответ будет [3, 7]. Поскольку он имеет все элементы между 3 и 7.
Я попытался ответить, но я не был убедителен. Подход, который я принял, состоял в том, чтобы сначала отсортировать список, а затем проверить его на самый большой интервал. Но меня попросили сделать это в O(n).
Я знаю решение, основанное на хэшировании и динамическом программировании. Пусть f (x) - хэш-функция. Трюк - это значение хеш-таблицы. Рассмотрим самый длинный интервал, содержащийся в списке, который начинается или заканчивается x. Затем h [f (x)] = y, где y является другим концом этого интервала. Обратите внимание, что длина этого интервала будет abs (x - y) + 1. В описании алгоритма будет понятно, почему сохранить это значение.
Перемещение по списку. Пусть i - текущий индекс, x: = list [i] - текущий номер. Теперь
1., если h [f (x)] не пуст, мы встретили число x раньше. Нечего делать, продолжайте.
2. Проверьте h [f (x-1)] и h [f (x + 1)].
2.1. Если они оба не пусты, это означает, что мы уже встретили x-1 и x + 1, и мы знаем несколько интервалов [a..x-1] и [x + 1..b], которые мы уже встречали в списке. Мы знаем это, потому что a = h [f (x-1)] и b = h [f (x + 1)] по определению h. Теперь, когда мы получили x, это означает, что мы теперь встретили весь интервал [a, b], поэтому мы обновляем значения следующим образом: h [f ( a)]: = b и h [f (b)]: = a.
Также установите h [f (x)] на некоторое значение (скажем x, чтобы не повлиять на ответ), так что в следующий раз мы встретим x в списке, мы игнорируем его. x уже выполнил свою работу.
2.2. Если задан только один из них, скажем h [f (x-1)] = a, то есть мы уже встретили некоторый интервал [a..x-1], и теперь он расширен с помощью x. Обновление будет h [f (a)]: = x и h [f (x)]: = a.
2.3. Если ни один из них не установлен, это значит, что мы не встретили ни x-1, ни x + 1, и самый большой интервал, содержащий x, который мы уже встретили, - это одиночный [x]. Поэтому установите h [f (x)]: = x.
Наконец, чтобы получить ответ, перейдите по всему списку и возьмите максимум abs (x - h [f (x)]) + 1 для всех x.
P.S. Я знаком с этой проблемой, потому что меня тоже попросили в интервью:)
Если сортировка нежелательна, вы можете использовать комбинацию хэш-карты и Структура данных с несвязанными наборами.
Для каждого элемента в списке создайте node и вставьте его в хэш-карту с ключом = значение элемента. Затем запросите хэш-карту для значения + 1 и значения-1. Если что-то найдено, скомбинируйте текущий node с множеством (наборами), в котором находятся соседние узлы. По завершении списка наибольший набор соответствует самому большому интервалу.
Сложность по времени - O (N * α (N)), где α (N) - обратная функция Аккермана.
Изменить: На самом деле Disjoint-set слишком силен для этой простой задачи. Решение Григора Геворкяна не использует его. Так что это проще и эффективнее.
Вы можете обменять пространство, чтобы получить это в линейном времени.
Первые шаги являются линейными в вашем списке. Последнее линейно по размеру A, которое может быть большим по сравнению с вашим списком, если у вас есть только несколько значений, которые находятся далеко друг от друга. Но, поскольку вы имеете дело с ints, A ограничено.
1 идея: ну, я думаю, вам придется сортировать список в любом случае, но вы не можете пойти с слиянием или быстрой сортировкой. Но если у вас есть память, вы можете использовать идею подсчет сортировки для целых чисел.
Итак, вы можете создать массив из 0 и 1, от 0 до максимального значения int, а затем заполнить его единицами, если у вас есть значение, а затем найти максимальный непрерывный массив
2 идея: создать словарь значений, найти min и max - все операции O (N):
dict = {1: 1, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 10: 10}
min = 1
max = 10
тогда, идем как i in range(min, max) и находим самое длинное непрерывное подмножество
>>> d = [1, 3, 5, 7, 4, 6, 10]
>>> s = set(d)
>>> mind = min(d)
>>> maxd = max(d)
>>> a, b, j = 0, 0, 0
>>> for i in range(mind, maxd):
if i not in s:
if (b - a) < (i - j - 1):
a, b = j, i - 1
j = i + 1
>>> a, b
(3, 7)
но это может быть медленным для разреженных списков, таких как [1, 9000, 100000]
РЕДАКТИРОВАТЬ: на основе великолепного ответа Григора Геворкяна, вот код для решения словаря O (N) в Python (я просто любите его простотой!!!)
l = [1, 3, 5, 7, 4, 6, 10]
d = {x:None for x in l}
print d
for (k, v) in d.iteritems():
if v is not None: continue
a, b = d.get(k - 1), d.get(k + 1)
if a is not None and b is not None: d[k], d[a], d[b] = k, b, a
elif a is not None: d[a], d[k] = k, a
elif b is not None: d[b], d[k] = k, b
else: d[k] = k
print d
m = max(d, key=lambda x: d[x] - x)
print m, d[m]
выход:
{1: None, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 3, 4: None, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 4, 4: 3, 5: None, 6: None, 7: None, 10: None}
{1: 1, 3: 5, 4: 3, 5: 3, 6: None, 7: None, 10: None}
{1: 1, 3: 6, 4: 3, 5: 3, 6: 3, 7: None, 10: None}
{1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: None}
{1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: 10}
3 7
Я разработал очень простое решение, используя HashSet. Поскольку contains и remove являются операциями O (1), вы можете просто создать новый интервал из случайного элемента набора и "развернуть" интервал до тех пор, пока вы не обнаружите его полный размер, удалив элементы из набора по мере продвижения, Удаление является ключевым, потому что это мешает вам "повторять" любые интервалы.
Это может помочь подумать об этом именно так: в списке есть K интервалов, размеры которых составляют до N. Ваша задача, таким образом, состоит в том, чтобы узнать, что представляют собой эти интервалы, без повторения каких-либо интервалов или элементов. Вот почему HashSet идеально подходит для работы - вы можете эффективно удалять элементы из набора при расширении ваших интервалов. Тогда вам нужно только следить за самым большим интервалом.
HashSeti = interval.start-1i, удалите i из набора и уменьшите как i, так и interval.startinterval.end)Вот решение в Java:
public class BiggestInterval {
static class Interval {
int start;
int end;
public Interval(int base) {
this(base,base);
}
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
public int size() {
return 1 + end - start;
}
@Override
public String toString() {
return "[" + start + "," + end + "]";
}
}
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(biggestInterval(Arrays.asList(1,3,5,7,4,6,10)));
}
public static Interval biggestInterval(List<Integer> list) {
HashSet<Integer> set = new HashSet<Integer>(list);
Interval largest = null;
while(set.size() > 0) {
Integer item = set.iterator().next();
set.remove(item);
Interval interval = new Interval(item);
while(set.remove(interval.start-1)) {
interval.start--;
}
while(set.remove(interval.end+1)) {
interval.end++;
}
if (largest == null || interval.size() > largest.size()) {
largest = interval;
}
}
return largest;
}
}
Это будет линейно, учитывая словари, построенные со средними хэш-таблицами O (1).
L = [1,3,5,7,4,6,10]
a_to_b = {}
b_to_a = {}
for i in L:
if i+1 in a_to_b and i-1 in b_to_a:
new_a = b_to_a[i-1]
new_b = a_to_b[i+1]
a_to_b[new_a] = new_b
b_to_a[new_b] = new_a
continue
if i+1 in a_to_b:
a_to_b[i] = a_to_b[i+1]
b_to_a[a_to_b[i]] = i
if i-1 in b_to_a:
b_to_a[i] = b_to_a[i-1]
a_to_b[b_to_a[i]] = i
if not (i+1 in a_to_b or i-1 in b_to_a):
a_to_b[i] = i
b_to_a[i] = i
max_a_b = max_a = max_b = 0
for a,b in a_to_b.iteritems():
if b-a > max_a_b:
max_a = a
max_b = b
max_a_b = b-a
print max_a, max_b
Трюк состоит в том, чтобы рассматривать элементы как набор, а не список. Это позволяет вам идентифицировать элементы, находящиеся в начале или конце смежных диапазонов, потому что набор позволяет проверить, присутствует ли элемент-1 или элемент + 1. При этом вы можете решить проблему в линейном времени и пространстве.
Псевдо-код:
Код С#:
static Tuple<int, int> FindLargestContiguousRange(this IEnumerable<int> items) {
var itemSet = new HashSet<int>(items);
// find contiguous ranges by identifying their starts and scanning for ends
var ranges = from item in itemSet
// is the item at the start of a contiguous range?
where !itemSet.Contains(item-1)
// find the end by scanning upward as long as we stay in the set
let end = Enumerable.Range(item, itemSet.Count)
.TakeWhile(itemSet.Contains)
.Last()
// represent the contiguous range as a tuple
select Tuple.Create(item, end);
// return the widest contiguous range that was found
return ranges.MaxBy(e => e.Item2 - e.Item1);
}
note: MaxBy находится в MoreLinq
Тестирование
Небольшая проверка работоспособности:
new[] {3,6,4,1,8,5}.FindLargestContiguousRange().Dump();
// prints (3, 6)
Большой непрерывный список:
var zeroToTenMillion = Enumerable.Range(0, (int)Math.Pow(10, 7)+1);
zeroToTenMillion.FindLargestContiguousRange().Dump();
// prints (0, 10000000) after ~1 seconds
Большой фрагментированный список:
var tenMillionEvens = Enumerable.Range(0, (int)Math.Pow(10, 7)).Select(e => e*2);
var evensWithAFewOdds = tenMillionEvens.Concat(new[] {501, 503, 505});
evensWithAFewOdds.FindLargestContiguousRange().Dump();
// prints (500, 506) after ~3 seconds
Сложность
Для этого алгоритма требуется время O (N) и O (N), где N - количество элементов в списке, предполагая, что заданные операции являются постоянными.
Обратите внимание, что если набор был задан как вход, вместо того, чтобы быть построенным алгоритмом, нам понадобилось бы только пространство O (1).
(Некоторые комментарии говорят, что это квадратичное время.Я думаю, что они приняли все элементы, а не просто элементы в начале диапазонов, вызвали сканирование. Это действительно было бы квадратично, если бы алгоритм работал именно так.)
Здесь решение похоже на Григора. Два основных отличия заключаются в том, что это решение сохраняет длину последовательного набора вместо других индексов и что это устраняет необходимость в последней итерации хеш-набора.
Итерации по массиву
Создайте хэш-карту, ища и обновляя соседние конечные точки:
Ключ - значения массива
Значение. Когда ключ является конечной точкой последовательного набора, сохраните длину этого набора. В противном случае, держите его правдивым, чтобы вы только рассматривали вещи один раз.
Если текущий заданный размер является самым длинным, обновите самый длинный заданный размер и самый длинный старт.
Здесь для ясности реализована реализация JavaScript, а также fiddle, чтобы увидеть ее в действии:
var array = [1,3,5,7,4,6,10];
//Make a hash of the numbers - O(n) assuming O(1) insertion
var longestSetStart;
var longestSetSize = 0;
var objArray = {};
for(var i = 0; i < array.length; i++){
var num = array[i];
if(!objArray[num]){//Only consider numbers once
objArray[num] = 1;//Initialize to 1 item in the set by default
//Get the updated start and end of the current set
var currentSetStart = num;//Starting index of the current set
var currentSetEnd = num;//Ending index of the current set
//Get the updated start of the set
var leftSetSize = objArray[num - 1];
if(leftSetSize){
currentSetStart = num - leftSetSize;
}
//Get the updated end of the set
var rightSetSize = objArray[num + 1];
if(rightSetSize){
currentSetEnd = num + rightSetSize;
}
//Update the endpoints
var currentSetSize = currentSetEnd - currentSetStart + 1;
objArray[currentSetStart] = currentSetSize;
objArray[currentSetEnd] = currentSetSize;
//Update if longest set
if(currentSetSize > longestSetSize){
longestSetSize = currentSetSize;
longestSetStart = currentSetStart;
}
}
}
var longestSetEnd = longestSetStart + longestSetSize - 1;
Я думаю, что я бы отсортировал их в списках последовательных целых чисел (при условии, что каждый номер может появиться только один раз)
взять первое число
если число 1 меньше или 1 больше, чем число в существующем списке?
yes: pre/post pend существующий список
no: создать новый список, начинающийся с текущего номера
если число больше, вернитесь вверх
отобразить самый длинный список
Отказ от ответственности: поскольку решение основано на хэш-таблицах, ожидается время работы, а не худший случай.
Это решение O (n) зависит от единственности целых чисел. Если они не уникальны, сделайте хешсет с вставкой O (1) и поиском членства и просто пропустите числа, которые уже встречались, когда вы проходите список.
Сделайте O (1) lookup/insert hashmap, где значения являются началами диапазонов, а ключи - это числа, которые соответствуют в конце этих диапазонов. Для значения v и ключа k это означает, что диапазон, начинающийся с v и заканчивающийся на k-1 включительно, находится в ключе k.
Пройдите список номеров. Для каждого числа n проверьте, имеет ли карта значение v в ключе n. Это соответствует тому, что существует диапазон, начинающийся с v, который позволит n в конце. Если есть, переместите v в ключ n + 1 и удалите запись с ключом n. Если диапазона нет, вставьте n в ключе n + 1.
Поскольку числа уникальны, ни один из диапазонов не перекрывается в конце, но могут быть некоторые смежные. Пропустите пары ключ/значение карты. Для каждого ключа k и значения v, если у карты есть значение v1 в ключе k1 = v, это означает, что существует диапазон от v1 до k-1. Вставьте v1 в k и удалите запись k1/v1.
Пройдите через записи k/v карты, чтобы найти наибольший диапазон [v, k-1] размера k-v, используя максимальный рабочий максимум.
В вашем примере:
setup:
l = [1,3,5,7,4,6,10]
m = {}
iteration:
process 1 : m = {2->1}
process 3 : m = {2->1, 4->3}
process 5 : m = {2->1, 4->3, 6->5}
process 7 : m = {2->1, 4->3, 6->5, 8->7}
process 4 : m = {2->1, 5->3, 6->5, 8->7}
process 6 : m = {2->1, 5->3, 7->5, 8->7}
process 10 : m = {2->1, 5->3, 7->5, 8->7, 11->10}
concatenation of contiguous ranges:
initial: m = {2->1, 5->3, 7->5, 8->7, 11->10}
first concatenation: m = {2->1, 7->3, 8->7, 11->10}, k=7, v=5, k1=5, v1=3
second concatenation: m = {2->1, 8->3, 11->10}, k=8, v=7, k1=7, v1=3
result:
largest range : [3,7] of size 5