1

アルゴリズム自体ではなく、実装であるアルゴリズム（最大値と最小値を見つけるため）に問題があります。説明させてください。

n = [0,1,1,2,3,5,8,13,-1,99]リストが;であるとしましょう。len(n) = 10 次に、globalMin, globalMax = n[0], n[0]＃リストから1回の反復をスキップします

そして今、私がしなければならないのは「ペア」で比較することです。すでにn [0]を使用しているので、n[1]とn[2]の比較を開始して、これら2つの間の最大値と最小値を見つけてから次のように比較します。 yグローバル最小、最大値、次にn[3]とn[4]、nmを私のグローバル値と比較し、次にn[5]とn[6] ..n[9]とn[を比較する必要があるまで10]、ご覧のとおり、n[10]は私のリストに存在しません。次のコードを使用してリストスライスでこれを解決できると思いました。

 for i in range(1, len(n), 2):

    if n[i:i+1] > n[i+1:i+2]:
      minl, maxl = n[i+1:i+2], n[i:i+1] # minl = local min; maxl = local max
    else:
      maxl, minl = n[i+1:i+2], n[i:i+1]

しかし、これは私の最後の要素が1つしかない場合（上記の例のように）は機能しないため、ご想像のとおり、minまたはmaxがリストの最後の要素である場合は無視されます。私はこれをインデックスまたはリストのスライスで修正しようとしていますが、まったく運がありません、何か提案はありますか？私はこれを「Pythonic」の方法で行う必要があり、インポートを使用せずにこれをできるだけ単純かつ短くするようにします。次の画像に基づくアルゴリズムの残りの部分を理解しました：画像

4

2 に答える 2

3

最初にリストの長さを確認できます。長さが奇数の場合は、リストの最後に最後の要素を追加できます。追加はO(1)操作であるため、時間の複雑さには影響しません。

whileループを使用できます。

In [78]: lis = [0,1,1,2,3,5,8,13,-1]

In [79]: if len(lis)%2 !=0 :  #if the list is of odd length then append the last item to it
    lis.append(lis[-1])
   ....:     

In [80]: i=0

In [81]: while i<len(lis)-1:
    if lis[i]>lis[i+1]:
        local_max,local_min=lis[i],lis[i+1]
    elif lis[i]<lis[i+1]:    
        local_max,local_min=lis[i+1],lis[i]
    else:
        local_max,local_min=lis[i],lis[i+1]
    print local_min,local_max
    i+=2
   ....:     
0 1
1 2
3 5
8 13
-1 -1

または、イテレータを使用できます。

In [86]: it=iter(lis)

In [87]: lis = [0,1,1,2,3,5,8,13,-1]

In [88]: if len(lis)%2 !=0 :
    lis.append(lis[-1])
   ....:     

In [89]: it=iter(lis)

In [90]: for _ in xrange(len(lis)/2):
   ....:     a,b=next(it),next(it)
   ....:     if a>b:
   ....:         local_max,local_min=a,b
   ....:     elif a<b:    
   ....:         local_max,local_min=b,a
   ....:     else:    
   ....:         local_max,local_min=a,b
   ....:     print local_min,local_max    
   ....:     
0 1
1 2
3 5
8 13
-1 -1
于 2013-03-08T01:08:35.083 に答える
2

私はこれがこれの最もPythonicな実装であると主張します：

from itertools import zip_longest

n = [0, 1, 1, 2, 3, 5, 8, 13, -1, 99]
global_min = global_max = n[0]

groups = [iter(n)] * 2
for a, b in zip_longest(*groups):
    if b is not None:
        if a > b:
            local_min, local_max = b, a
        else:
            local_min, local_max = a, b
    else:
        local_min = local_max = a
    if local_min < global_min:
        global_min = local_min
    if local_max > global_max:
        global_max = local_max

print(global_min, global_max)

itertools.zip_longest()（itertools.izip_longest()2.x）を使用してアイテムをグループ化し、同じイテレータのリストを繰り返します。次に、これをループして、値をペアで取得します。次に、チェックを実行します。値が最後の値である場合は、local_minおよびlocal_maxとして割り当てます。それ以外の場合は、2つの値を比較して、必要に応じて割り当てます。

次に、とを比較（および場合によっては更新）global_minしglobal_maxます。

于 2013-03-08T01:21:44.200 に答える