2

組み込み関数や関数を使用せずに、[0,0,1,0,1,1,0]要素が0＆のみであるリストを並べ替える最も効率的な方法は何ですか。O（n）以下1sort()sorted()count()

4

10 に答える 10

11 
>>> lst = [0,0,1,0,1,1,0]
>>> l, s = len(lst), sum(lst)
>>> result = [0] * (l - s) + [1] * s
>>> result
[0, 0, 0, 0, 1, 1, 1]
于 2012-06-24T07:21:47.800 に答える
4

使用できる一般的な並べ替えアルゴリズムは多数あります。ただし、この場合、最も重要な考慮事項は、並べ替えるすべての要素がセット（0,1）に属することです。

他の寄稿者が答えたように、些細な実装があります。

def radix_sort(a):
    slist = [[],[]]
    for elem in a:
        slist[elem].append(elem)
    return slist[0] + slist[1]

print radix_sort([0,0,1,0,1,1,0])

これは基数ソートの特定の実装であることに注意する必要があります。また、ソートされるリストの要素が定義された限定セットに属している場合、これは簡単に拡張できます。

def radix_sort(a, elems):
    slist = {}
    for elem in elems:
        slist[elem] = []
    for elem in a:
        slist[elem].append(elem)
    nslist = []
    for elem in elems:
        nslist += slist[elem]
    return nslist

print radix_sort([2,0,0,1,3,0,1,1,0],[0,1,2,3])

sort()または機能がありませんsorted()。count()の上）

于 2012-06-24T07:36:47.973 に答える
2

これは次のとおりですO(n)(これより少なくすることはできません)。

old = [0,0,1,0,1,1,0]
zeroes = old.count(0) #you gotta count them somehow!
new = [0]*zeroes + [1]*(len(old) - zeroes)

Python ループがないため、これは純粋な Python で取得できる速度が速い可能性があります...

于 2012-06-24T07:21:56.660 に答える
1

def sort_arr_with_zero_one():

  main_list = [0,0,1,0,1,1,0]
  zero_list = []
  one_list = []
  for i in main_list:
    if i:
        one_list.append(i)
    else:
        zero_list.append(i)

  return zero_list + one_list
于 2012-06-24T07:26:50.210 に答える
0

知っておく必要があるのは、元のシーケンスの長さとその中にあるシーケンスの数だけです。

old = [0,0,1,0,1,1,0]
ones = sum(1 for b in old if b)
new = [0]*(len(old)-ones) + [1]*ones
于 2012-06-24T10:33:57.347 に答える
0

値が 2 つしかないため、出力の正確な構造が事前にわかっています。長さの異なる 2 つの領域に分割されます。

于 2012-06-24T07:16:47.520 に答える
0

私はJBernadoによる答えが好きですが、別の巨大なオプションをスローします（ただし、プロファイリングは行っていません-辞書ハッシュの順序に依存しているため、特に拡張可能ではありませんが、0と1で機能します）：

from itertools import chain, repeat
from collections import Counter

list(chain.from_iterable(map(repeat, *zip(*Counter(bits).items()))))

または - 少し複雑ではありません...

from itertools import repeat, chain, islice, ifilter
from operator import not_

list(islice(chain(ifilter(not_, bits), repeat(1)), len(bits)))

これにより、すべてが C レベルに維持されるため、かなり最適なはずです。

于 2012-06-24T10:26:14.410 に答える
0

私はこれを試してみます：

b = [0,0,1,0,1,1,0]

def odd_sort(a):
  zeroes = a.count(0)

  return [0 for i in xrange(zeroes)] + [1 for i in xrange(len(a) - zeroes)]
于 2012-06-24T07:22:21.300 に答える
0

i開始 ( ) と終了 ( )からの 2 つのポインターを使用してリストをたどりj、値を 1 つずつ比較し、必要に応じてそれらを交換できます。

def sort_binary_values(l):
    i, j = 0, len(l)-1
    while i < j:
        # skip 0 values from the begin
        while i < j and l[i] == 0:
            i = i+1
        if i >= j: break
        # skip 1 values from the end
        while i < j and l[j] == 1:
            j = j-1
        if i >= j: break
        # since all in sequence values have been skipped and i and j did not reach each other
        # we encountered a pair that is out of order and needs to be swapped
        l[i], l[j] = l[j], l[i]
        j = j-1
        i = i+1
    return l
于 2012-06-24T07:25:17.473 に答える