給定一個整數列表，確定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

對於小列出了此爲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

這是一個算法，需要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] 

幾種優化，包括改變迭代順序都是可能的。

Answer 4

下面是一個已經排序的陣列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。