-3

プログラムは、クイック選択を使用して、一連の整数値の中央値を返すことになっています。

質問: プログラムを実行すると、k が定義されていないと表示されます。中央値を取得するには、k をどのように定義すればよいですか?

def quickSelect(lines,k):
    if len(lines)!=0:
        pivot=lines[(len(lines)//2)]
        smallerlist=[]
        for i in lines:
            if i<pivot:
                smallerlist.append(i)
        largerlist=[]
        for i in lines:
            if i>pivot:
                largerlist.append(i)
        m=len(smallerlist)
        count=len(lines)-len(smallerlist)-len(largerlist)
        if k >= m and k<m + count:
            return pivot
        elif m > k:
            return quickSelect(smallerList,k)
        else:
            return quickSelect(largerList, k - m - count)
4

3 に答える 3

0

マイナーな修正の後、コードは正常に機能しているようです。smalllist と largelist にタイプミスがありました。

        elif m > k:
            return quickSelect(smallerList,k)
        else:
            return quickSelect(largerList, k - m - count)

によって変更する必要があります

        elif m > k:
            return quickSelect(smallerlist,k)
        else:
            return quickSelect(largerlist, k - m - count)

これは最終的に修正されたコードで、問題なく動作します。

def quickSelect(lines,k):
    if len(lines)!=0:
        pivot=lines[(len(lines)//2)]
        smallerlist=[]
        for i in lines:
            if i<pivot:
                smallerlist.append(i)
        largerlist=[]
        for i in lines:
            if i>pivot:
                largerlist.append(i)
        m=len(smallerlist)
        count=len(lines)-len(smallerlist)-len(largerlist)
        if k >= m and k<m + count:
            return pivot
        elif m > k:
            return quickSelect(smallerlist,k)
        else:
            return quickSelect(largerlist, k - m - count)

それが役に立てば幸い

于 2014-03-04T23:01:28.577 に答える
-1

エラーを誤って報告しました。について文句を言うのではなく、(lower-case-l)を定義してから大文字の L で呼び出そうとしたためk、文句を言います。Python 変数は大文字と小文字が区別されます。smallerListsmallerlistsmallerlist is smallerList == False

あなたのコードを見る：

def quickSelect(lines, k):
    if len(lines) != 0:

len(lst) != 0非慣用的です。lstPEP-8 は、 のようにであるべきだと言っていif lst:ます。また、camelCase は非 Pythonic です。関数名はquick_select. linesテキストのみを操作できることを意味しますが、関数は順序付け可能なデータ型でも同様に機能するため、itemsより正確になります。次の人がそれが何をするかを理解できるように、docstring を持っている必要があります。len(items)もう一度呼び出すので、一度呼び出して結果を保存することもできます。最後に、もしk > len(items)?

def quick_select(items, k):
    """
    Return the k-from-smallest item in items

        Assumes 0 <= k < len(items)
    """
    num_items = len(items)
    if 0 <= k < num_items:
        pivot = items[num_items // 2]

継続:

        smallerlist = []
        for i in lines:
            if i<pivot:
                smallerlist.append(i)
        largerlist=[]
        for i in lines:
            if i>pivot:
                largerlist.append(i)

lines2 回繰り返しました。これを 1 つのパスに組み合わせることができます。また、より良い変数名:

        smaller, larger = [], []
        for item in items:
            if item < pivot:
                smaller.append(item)
            elif item > pivot:
                larger.append(item)

より良い変数名を継続し、

        num_smaller = len(smaller)
        num_pivot = num_items - num_smaller - len(larger)

次に、あなたifのは故障しています。順番に読みやすいので、

        if k < num_smaller:
            return quick_select(smaller, k)
        elif k < num_smaller + num_pivot
            return pivot
        else:
            return quick_select(larger, k - num_smaller - num_pivot)

k < 0 または k >= num_items の場合はどうなるでしょうか?:

    else:
        raise ValueError("k={} is out of range".format(k))

最後に、この関数は末尾再帰であるため、代わりに反復関数に変換するのは簡単です。

        while True:
            pivot = items[num_items // 2]

            # ...

            if k < num_smaller:
                items = smaller
                num_items = num_smaller
            elif k < num_smaller + num_pivot
                return pivot
            else:
                items = larger
                num_items = num_larger
                k -= num_smaller + num_pivot

... 組み立てが必要です。お役に立てば幸いです。

于 2014-03-05T02:53:02.197 に答える
-1

関数に初めて k を初期化する必要があります。これは、探している項目の位置である必要があります (リストがソートされている場合)。中央値の場合、デフォルトでリストの長さの半分になります。次のように呼び出します。

k = len(lines) // 2
x = quickSelect(lines, k)

または、中央値のみが必要な場合は、関数を修正して、必要なアイテムのインデックスを提供する必要がないようにすることができます

def quickSelect(lines, k=None):
    if k is None:
        k = len(lines)//2

Hugh が指摘したように、この関数はリストの要素のみを選択します。偶数要素の中央値の場合、中央値は実際には中央の 2 つの要素の平均になります。

于 2014-03-04T23:04:19.993 に答える