相关疑难解决方法(0)

我相信有一种方法可以在O(n)中找到长度为n的未排序数组中的第k个最大元素.或许它是"预期的"O(n)或其他东西.我们应该怎么做？

我正在学习Python,并且处理列表的简单方法是一种优势.有时它是,但看看这个:

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> numbers.remove(max(numbers))
>>> max(numbers)
74

从列表中获取第二大数字的一种非常简单,快捷的方法.除了简单列表处理有助于编写两次遍历列表的程序,找到最大的然后是第二大的.它也具有破坏性 - 如果我想保留原始数据,我需要两份数据.我们需要:

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> if numbers[0]>numbers[1]):
...    m, m2 = numbers[0], numbers[1]
... else:
...    m, m2 = numbers[1], numbers[0]
...
>>> for x in numbers[2:]:
...    if x>m2:
...       if x>m:
...          m2, m = m, x
...       else:
...          m2 = x
...
>>> m2
74

它只运行一次列表,但不像以前的解决方案那样简洁明了.

那么:在这样的情况下,有没有办法让两者都有？第一个版本的清晰度,但第二个版本的单个运行？

我想解决这个问题..

给定n个数字列表,我们希望从列表中找到最小和最小的数字.描述一种分而治之的算法来解决这个问题.假设对于整数k,n = 2 ^ k.使用算法的比较次数不应超过3n/2 - 2,即使在最坏的情况下也是如此.

我目前的解决方案是使用选择算法来获得中位数,然后将列表分成L1(包含小于或等于中位数的元素),R(中位数),L2(包含比中位数更大的所有元素).这是对的吗？如果是这样,接下来该怎么办？