Объединение интервалов
Вы можете использовать Object.prototype.hasOwnProperty ()
var findInEnum,
colorEnum = {
red : 0,
green : 1,
blue : 2
};
// later on
findInEnum = function (enumKey) {
if (colorEnum.hasOwnProperty(enumKey)) {
return enumKey+' Value: ' + colorEnum[enumKey]
}
}
alert(findInEnum("blue"))3 ответа
Отсортируйте их по одному из терминов (например, начало), затем проверьте на перекрытия со своим (правым) соседом при перемещении по списку.
class tp():
def __repr__(self):
return '(%d,%d)' % (self.start, self.end)
def __init__(self,start,end):
self.start=start
self.end=end
s=[tp(5,10),tp(7,8),tp(0,5)]
s.sort(key=lambda self: self.start)
y=[ s[0] ]
for x in s[1:]:
if y[-1].end < x.start:
y.append(x)
elif y[-1].end == x.start:
y[-1].end = x.end
Отсортировать все точки. Затем просмотрите список, увеличивая счетчик для «начальных» точек и уменьшая его для «конечных» точек. Если счетчик достигает 0, то это действительно конечная точка одного из интервалов в объединении.
Счетчик никогда не станет отрицательным и достигнет 0 в конце списка.
Используйте ] алгоритм развертки линии . По сути, вы сортируете все значения в списке (сохраняя, является ли он началом или концом интервала вместе с каждым элементом). Это операция O (n log n). Затем вы выполняете цикл за один проход по отсортированным элементам и вычисляете интервалы O (n).
O (n log n) + O (n) = O (n log n)