数字のリストの最初の3つの最小値を見つける方法

Question

リストをソートせずに、要素を削除せずに数字のリストの最初の3つまたは4つの小さな数字を見つける方法を知りたい。つらい時私に最小の第三または第四の最小数を与えるためにコードを変更した、しかし、私は

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 

：最初の2つの最小の数値（分）を求める細かい仕事をしてその下にいくつかのコードを、私を発見しました。

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 

任意の提案をしてください：ここに私の変更されたコードは、その下に、時々ではなく、すべての時間を動作しているようですか？最悪の場合、線形時間でソートされていない要素の配列にk番目の最大値/最小値を見つけるため

Answer 1

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 

これは3番目に小さいです。 4番目に小さいものについても同様のロジックを適用できます。実際には、リストm1、m2、m3はソートされたリストであり、xが境界内にある場合は、このリストにxを挿入する各要素を反復処理します。

このロジックをn番目の要素に拡張するには、挿入ソートロジックを使用して、m1.m2.m3..m _nリストにxを挿入します。

Answer 2

このアルゴリズムを使用することができます。

kthSmallest（ARR [0..N-1]、K）

1）arr []を⌈n/ 5rceilに分割します。グループ ここで、 が5個未満の要素を有する最後のグループを除いて、各グループのサイズは5である。

2）上記の⌈n/5⌉グループをソートし、すべて グループの中央値を見つけます。補助配列 'median []'を作成し、このメディアン配列に すべての⌈n/5⌉個のグループを格納します。

//再帰的中央値の中央値を見つけるために、このメソッドを呼び出す[0..⌈n/5⌉-1] 3）medOfMed = kthSmallest（メジアン[0..⌈n/5⌉-1]、 4）medOfMedの周囲にarr []を配置し、その位置を取得する。 POS =パーティション（ARR、N、medOfMed）

5）POS == Kリターン6をmedOfMed場合）、POS < Kリターン場合 kthSmallest（ARR [l..pos-1]、K）7）POA場合> k個のリターン kthSmallest（ARR [POS + 1..r]、K-POS + L-1）

Hereあなたは（最悪の場合には線形時間の証明と）完全な説明を見つけることができますし、 C++での実装