最大 K 数問題に対する Python の解決策

TopK 問題、つまり最大の K 数を見つけるこの問題は、1,000 万件の検索レコードから最も人気のある 10 個のキーワードを見つけるなど、非常に一般的です。 k 個の数値。
時間計算量: O(n*logn)+O(k)=O(n*logn)。

方法 2: 最大ヒープ

最小の K 数値を格納するためにサイズ K のデータ コンテナーを作成し、配列全体を走査し、各数値をコンテナー内の最大の数値と比較します (この数値がコンテナ内の最大値より大きい場合は、トラバースを続行します。それ以外の場合は、コンテナ内の最大値をこの数値に置き換えます。この方法を理解するのは非常に簡単です。コンテナの選択に関して、多くの人は最大ヒープを思い浮かべますが、Python で最大ヒープを実装するにはどうすればよいでしょうか。最小ヒープを実装する heapq ライブラリを使用できます。これは、配列内で各数値を反転すると、最大数値が最小数値になり、数値全体の順序が変わるため、配列内の各数値を反転できるためです。を使用し、最終的に結果を返すときに最小ヒープを使用して結果を否定します。 コードは次のとおりです。

メソッド 3: クイック選択

クイック選択アルゴリズムと似ています。重要なのは、クイック選択は各トリップで一方向にのみ実行する必要があるということです。

import heapq
def get_least_numbers_big_data(self, alist, k):
  max_heap = []
  length = len(alist)
  if not alist or k <= 0 or k > length:
    return
  k = k - 1
  for ele in alist:
    ele = -ele
    if len(max_heap) <= k:
      heapq.heappush(max_heap, ele)
    else:
      heapq.heappushpop(max_heap, ele)

  return map(lambda x:-x, max_heap)


if __name__ == "__main__":
  l = [1, 9, 2, 4, 7, 6, 3]
  min_k = get_least_numbers_big_data(l, 3)

最大の Python バージョンに関するその他の関連記事については、 K 数の問題は、PHP の中国語 Web サイトに注意してください。