如何用O(n)解求第n个最大数

Question

你能告诉我我的代码有什么问题吗：

问题描述：程序首先接收整数n，然后接收浮点值列表。以一个小数点的精度打印列表中第n个最大的元素。

注：第n个最大元素，而不仅仅是第n个元素。N是列表的长度。

示例输入：2 1.0 2.0 3.0 4.0 5.0输出：4.0

numbers = input()
a = numbers.split() 
n = int(a[0]) 
b = sorted(a[1:])
n_th_largest =float(b[-n]) 
e = "{:.1f}".format(n_th_largest)
print(e)

Answer 1

你能告诉我我的代码出了什么问题吗

您对字符串进行排序，因此例如'2.0'将被视为大于'13.0'，因为字符'2'大于字符'1'。所以你会得到一个错误的顺序，从而得到错误的结果。

按float值排序的一种方法是使用一个关键函数：

b = sorted(a[1:], key=float)

或者先转换为浮点，然后对这些浮点进行排序：

b = sorted(map(float, a[1:]))

在这种情况下，您不需要额外的转换来浮动在下一行中。

---

对于O(N(。。。这是可能的，正如近50年前所示，但绝非微不足道。即使你已经知道如何做，也不容易做到。而且问题描述实际上并没有要求。但如果你想做，可以看看维基百科的选择算法页面或那篇论文，或者一本涵盖该主题的算法入门教材，例如CLRS的算法入门。

Answer 2

您可以根据一系列可能的值对O(n(时间复杂性和O(n(内存使用计数排序。它本质上是一种散列技术。注意，在时间复杂度和O(1(内存方面不可能做到O(n(。以下是链接来源的一些代码：

# python program for counting sort
def countingSort(arr):
size = len(arr)
output = [0] * size
# count array initialization
count = [0] * 10
# storing the count of each element 
for m in range(0, size):
count[arr[m]] += 1
# storing the cumulative count
for m in range(1, 10):
count[m] += count[m - 1]
# place the elements in output array after finding the index of each element of original array in count array
m = size - 1
while m >= 0:
output[count[arr[m]] - 1] = arr[m]
count[arr[m]] -= 1
m -= 1
for m in range(0, size):
arr[m] = output[m]
data = [3,5,1,6,7,8,3]
countingSort(data)
print("Sorted Array: ")
print(data)