1

Python のリストの最後の要素を適切な位置に移動する効率的な方法を探しています。たとえば、list = [1, 3, 4, 5, 6, 2] の場合、list = [1, 2, 3, 4, 5, 6] を取得する必要があります。私が試したことは、望ましい方法では機能しません:

    def sort1(lng, lst):
        if len(lst) != lng:
            return
        else:
            i = -2
            last = lst[-1]
            for x in lst:
                if last < lst[i]:
                    lst[i] = last
                    i -= 1
                    print(lst)
    sort1(6,[1,3,4,5,6,2])


It is giving me following result:
   [1, 3, 4, 5, 2, 2]
   [1, 3, 4, 2, 2, 2]
   [1, 3, 2, 2, 2, 2]
   [1, 2, 2, 2, 2, 2]
4

4 に答える 4

6

リストからアイテムをポップし、次を使用して挿入し直しますbisect.insort_left。

>>> import bisect
>>> lst = [1, 3, 4, 5, 6, 2]
>>> item = lst.pop()
>>> bisect.insort_left(lst, item)
>>> lst
[1, 2, 3, 4, 5, 6]
于 2015-01-28T14:51:53.173 に答える
0

@Ashwiniの回答ほどセクシーではありませんが、これを試すことができます。

それ以外の：

    lst[i] = last

（下に移動すると、配列全体が最後の値で上書きされます）

これを行う：

    lst[i+1] = lst[i]

(これにより、すべての値がシフトされます)

次に、すべてのループの後:

    lst[i+1] = last

(最後の値を正しい位置に置きます。これは i+1 があるべき場所です)

于 2015-01-28T14:59:48.130 に答える
0

独自の関数を作成する必要がある場合は、enumerate を使用して、ele が 2 つの値の間にある場所、または最初の値以下の場所を見つけることができます。

def sor1(lst):
    # empty or list with single ele or  last ele is larger than second last the list os sorted
    if len(lst) < 2 or lst[-1] > lst[-2]:
        return lst
    last = lst.pop()
    # if first value is larger than the last we need to insert last before the first
    if lst[0] >= last:
        lst.insert(0, last)
        return lst
    # else find first place where last falls between two values
    for ind, ele in enumerate(lst):
        if ele <= last <= lst[ind+1]:
            lst.insert(ind+1,last)
            return lst

挿入があるblistライブラリもあり0(log n)、他の python リスト操作よりも優れています。逆の場合もあるため、何をしたいかによって異なります。

from blist import blist
lst =  blist([1, 3, 4, 5, 6, 2])

リストよりもブリストの方が効率的ないくつかの操作:

  • リストへの挿入またはリストからの削除 O(log n) O(n)

  • リストへの挿入またはリストからの削除 O(log n) O(n)

  • リストのスライスを取る O(log n) O(n)

  • リストの浅いコピーの作成 O(1) O(n)

  • リストのスライスの変更 O(log n + log k) O(n+k)

  • リストを乗算してスパース リストを作成する O(log k) O(kn)

  • bisect.insort O(log**2 n) O(n) でソートされたリストを維持する

Python 2.7 を使用して insort_left を使用したリストよりもわずかに優れています。

In [32]: %%timeit
lst = list(range(1000000))+[90000]
item = lst.pop()
bisect.insort_left(lst, item)
   ....: 
10 loops, best of 3: 38.5 ms per loop

In [33]: %%timeit
lst = blist(range(1000000))+blist([90000])
item = lst.pop()
bisect.insort_left(lst, item)
   ....: 
10 loops, best of 3: 27.9 ms per loop
于 2015-01-28T15:00:58.700 に答える