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

これは、すでにソートされている配列の単純な線形時間アルゴリズム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、実行時間は常に線形です。middlehigh1length(a)length(a)

の一致するサブシーケンスが必要な場合は、 の代わりにa出力できます。a[low]...a[high]true

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

これは時間がかかるアルゴリズムです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]

反復順序の変更など、いくつかの最適化が可能です。