Учитывая список целых чисел, определите, находятся ли 70% значений в пределах 20% от одного из значений

Question

Я хочу проверить, имеют ли значения списка какой-то уровень "близости". Есть хороший алгоритм для этого? Бонусные баллы за самый питонический способ.

действительный

[1,7,8,9]
[3,4,100,101,102,103,104,105]

Недействительный

[1,8,9]
[1,10]
[100,200,300,400,500]

Answer 1

Для небольших списков этого алгоритма O(n^2) будет достаточно:

def is_close(l):
    for n in l:
        c = sum([1 for x in l if x >= 0.8 *n and x <= 1.2 * n])
        if c >= 0.7 * len(l):
            return True
    return False

print is_close([1,7,8,9])
print is_close([3,4,100,101,102,103,104,105])
print is_close([1,8,9])
print is_close([1,10])
print is_close([100,200,300,400,500])

Выход:

True
True
False
False
False

Answer 2

Посмотрите на разницу: http://en.wikipedia.org/wiki/Variance

Answer 3

Вот простой линейно-временной алгоритм для массива a это уже отсортировано (как в примерах, в противном случае его нужно предварительно отсортировать в O(n log n) время). Идея состоит в том, чтобы построить и проверить каждую максимальную подпоследовательность, которая начинается в данной позиции low,

low = middle = high = 1
while (low <= length (a))
   advance middle to the largest i such that a[i]*0.8<=a[low]
   advance high to the largest i such that a[i]<=a[middle]*1.2
   if ((high-low+1)/length(a)>=0.7) output(true)
   low = low + 1
return (false);

поскольку low, middle, а также high всегда увеличиваются с 1 через length(a)время работы всегда линейно в length(a),

Если соответствующая подпоследовательность a желательно, можно вывести a[low]...a[high] вместо true,

Answer 4

Вот алгоритм, который принимает n logn время.

sort the array
for i in range(len(array))
    begin = binary search an index such that array[begin] >= array[i]*0.2
    end = binary search an index such that array[end]*0.2 <= array[i]
    if (end - begin) <= len(array) * 0.7
        70% of the values are within %20 of array[i]
        i.e all elements between begin and end are within 20% of array[i]

Возможны несколько оптимизаций, включая изменение порядка итераций.