如何找到数字列表的前 3 个最小值

Question

我想知道如何在不对列表进行排序和删除元素的情况下找到数字列表中的前 3 或 4 个最小数字。我在下面找到了一些代码，可以很好地找到前 2 个最小数字（分钟）：

def second_smallest(numbers):
    m1, m2 = float('inf'), float('inf')
    for x in numbers:
        if x <= m1:
            m1, m2 = x, m1
        elif x < m2:
            m2 = x
    return m2

但是，我很难修改代码来给我第三小或第四小的数字。下面是我修改后的代码，它似乎有时有效但并非始终有效：

m1, m2, m3= float('inf'), float('inf'), float('inf')
    for x in min_of_summed_vals:
        if x < m1:
            m1, m2 = x, m1
        elif x < m2:
            m2 = x
        elif x > m2 and x < m3:
            m3 = x

有什么建议吗？

Answer 1

您可以使用此算法找到第 k 个 maximum/minimum 到具有最坏情况线性时间的未排序元素数组：

kthSmallest(arr[0..n-1], k)

1) Divide arr[] into ⌈n/5rceil; groups where size of each group is 5 except possibly the last group which may have less than 5 elements.

2) Sort the above created ⌈n/5⌉ groups and find median of all groups. Create an auxiliary array 'median[]' and store medians of all ⌈n/5⌉ groups in this median array.

// Recursively call this method to find median of median[0..⌈n/5⌉-1] 3) medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

4) Partition arr[] around medOfMed and obtain its position. pos = partition(arr, n, medOfMed)

5) If pos == k return medOfMed 6) If pos < k return kthSmallest(arr[l..pos-1], k) 7) If poa > k return kthSmallest(arr[pos+1..r], k-pos+l-1)

Here 你可以找到完整的解释（证明最坏情况下的线性时间）和 C++ 实现

Answer 2

def third_smallest(numbers):
    m1, m2, m3 = float('inf'), float('inf'), float('inf')
    for x in numbers:
        if x <= m1:
            m1, m2, m3 = x, m1, m2
        elif x < m2:
            m2, m3 = x, m2
        elif x < m3:
            m3 = x
    return m3

这应该适用于第三小。您可以对第四小应用类似的逻辑。实际上，列表 m1、m2、m3 是一个排序列表，如果 x 落在边界内，则迭代您在此列表中插入 x 的每个元素。

要将此逻辑扩展到第 n 个元素，您可以使用插入排序逻辑将 x 插入到 m1.m2.m3..m_n 列表中。

如何找到数字列表的前 3 个最小值

How to find the first 3 minimums of a list of numbers

loops

for-loop

numbers

list

min