1

除了 len() 或 range() 之外，请不要使用内置插件。我正在准备期末考试。

这是我的意思的一个例子。

def find_numbers(x, lst):


lst = [3, 8, 1, 2, 0, 4, 8, 5]

find_numbers(3, lst) # this should return -> (1, 6, 7)

我没有完全尝试过....无法找出最好的解决方法：

def find_K_highest(lst, k):
 newlst = [0] * k
 maxvalue = lst[0]


 for i in range(len(lst)):
    if lst[i] > maxvalue:
        maxvalue = lst[i]
        newlst[0] = i
4

4 回答 4

5

从列表中取出前 3 (x) 个数字。最大值的最小值是这些。在您的情况下：3、8、1。它们的索引是（0、1、2）。构建它们的对（（3,0），（8,1），（1,2））。

现在按最大值的大小对它们进行排序：((8,1), (3,0), (1,2))。

使用这个初始列表，您可以递归地遍历列表的其余部分。将最小值 (1, _) 与列表中的下一个元素 (2, 3) 进行比较。如果它更大（它是），将其排序到列表（（8,1），（3,0），（2,3））中并丢弃最小的。

一开始你在前三名中有很多变化，但后来，它们变得很少。当然，遍历时，您还必须保留有关最后位置（3、4、5，...）的书。

前 N 个元素的插入排序应该非常高效。

这是 Scala 中的类似问题，但不需要报告索引。

于 2012-05-12T02:50:30.287 回答
1

我不知道发布解决方案是否很好，但这似乎可行：

def find_K_highest(lst, k):
    # escape index error
    if k>len(lst):
        k=len(lst)
    # the output array
    idxs = [None]*k
    to_watch = range(len(lst))
    # do it k times
    for i in range(k):
        # guess that max value is at least at idx '0' of to_watch
        to_del=0
        idx = to_watch[to_del]
        max_val = lst[idx]
        # search through the list for bigger value and its index
        for jj in range(len(to_watch)):
            j=to_watch[jj]
            val = lst[j]
            # check that its bigger that previously finded max
            if val > max_val:
                idx = j
                max_val = val
                to_del=jj
            # append it
        idxs[i] = idx
        del to_watch[to_del]
        # return answer
    return idxs

PS我试图解释每一行代码。

于 2012-05-12T02:55:46.587 回答
1

你可以使用列表方法吗？（例如append，，？）sort。index如果是这样，这应该有效（我认为......）

def find_numbers(n,lst):
    ll=lst[:]
    ll.sort()
    biggest=ll[-n:]
    idx=[lst.index(i) for i in biggest] #This has the indices already, but we could have trouble if one of the numbers appeared twice
    idx.sort()
    #check for duplicates.  Duplicates will always be next to each other since we sorted.
    for i in range(1,len(idx)):
       if(idx[i-1]==idx[i]):
         idx[i]=idx[i]+lst[idx[i]+1:].index(lst[idx[i]]) #found a duplicate, chop up the input list and find the new index of that number
         idx.sort()
    return idx

lst = [3, 8, 1, 2, 0, 4, 8, 5]

print find_numbers(3, lst)
于 2012-05-12T03:12:56.207 回答
1

老兄。你有两种方法可以解决这个问题。

第一种方法是聪明。把你的老师赶出去。她正在寻找的是递归。您可以在没有递归和没有内置函数或方法的情况下编写此代码：

#!/usr/bin/python

lst = [3, 8, 1, 2, 0, 4, 8, 5]

minval=-2**64

largest=[]

def enum(lst): 
    for i in range(len(lst)): 
        yield i,lst[i]

for x in range(3):
    m=minval
    m_index=None
    for i,j in enum(lst):
        if j>m: 
            m=j
            m_index=i

    if m_index:        
        largest=largest+[m_index]
        lst[m_index]=minval       

print largest

这行得通。它很聪明。带那个老师！！！但是，你会得到一个C或更低的......

或者——你可以成为老师的宠物。写成她想要的样子。您将需要一个列表的递归最大值。剩下的很简单！

def max_of_l(l):
    if len(l) <= 1:
        if not l:
            raise ValueError("Max() arg is an empty sequence")
        else:
            return l[0]
    else:
        m = max_of_l(l[1:])
        return m if m > l[0] else l[0]

print max_of_l([3, 8, 1, 2, 0, 4, 8, 5])
于 2012-05-12T03:59:29.600 回答