-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

您误报了错误；它不抱怨k，它抱怨是smallerList因为你定义了smallerlist（小写-l），然后尝试用大写-L 来调用它。Python 变量区分大小写，即smallerlist is smallerList == False.

查看您的代码：

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

len(lst) != 0是非惯用语；PEP-8 说它应该只是lst，如if lst:. 此外，camelCase 是非 Pythonic 的；你的函数名应该是quick_select. lines意味着您只能对文本进行操作，但您的函数应该同样适用于任何可排序的数据类型，因此items会更准确。您应该有一个文档字符串，以便下一个来的人知道它的作用，我们将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)

你已经迭代了lines两次；你可以把它组合成一个单程。此外，更好的变量名称：

        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的 s 出了问题；它们更容易按顺序阅读，所以

        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 所指出的，这个函数只会选择列表中的一个元素。对于偶数个元素的中位数，中位数实际上应该是中间两个元素的平均值。

于 2014-03-04T23:04:19.993 回答