python - 给定一个整数列表，确定 70% 的值是否在其中一个值的 20% 范围内

Question

我想检查列表值是否具有某种程度的“接近性”。有没有一个好的算法来做到这一点？最pythonic方式的奖励积分。

有效的

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

无效

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

Answer 1

查找方差：http ://en.wikipedia.org/wiki/Variance

Answer 2

对于小列表，这个 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 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总是从1through增加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]

可以进行多种优化，包括更改迭代顺序。