최대 K 수 문제에 대한 Python 솔루션

TopK 문제, 즉 가장 큰 K 숫자를 찾는 문제입니다. 천만 검색 기록에서 가장 인기 있는 키워드 10개를 찾는 등 매우 흔한 문제입니다.

방법 1:
먼저 정렬한 다음 처음 k개 숫자를 가로챕니다.
시간 복잡도: O(n*logn)+O(k)=O(n*logn).
이 방법은 비교적 간단하고 투박하니 언급만 해주세요.

방법 2: 최대 힙

K 크기의 데이터 컨테이너를 만들어 가장 작은 K 숫자를 저장한 다음 전체 배열을 반복하고 각 숫자를 추가할 수 있습니다. 이를 컨테이너의 최대값과 비교합니다. 이 숫자가 컨테이너의 최대값보다 크면 계속 이동하고, 그렇지 않으면 컨테이너의 최대값을 이 숫자로 바꿉니다. 이 방법에 대한 이해도 매우 간단합니다. 컨테이너를 선택할 때 많은 사람들의 첫 번째 반응은 최대 힙입니다. 그런데 Python에서 최대 힙을 구현하는 방법은 무엇입니까? 최소 힙을 구현한 heapq 라이브러리를 사용할 수 있는 이유는 배열에서 각 숫자를 반전시키면 최대 숫자가 최소 숫자가 되고 전체 숫자의 순서가 바뀌므로 배열의 각 숫자가 반전될 수 있기 때문입니다. , 그리고 최종적으로 결과를 반환할 때 최소 힙을 사용하여 결과를 무효화합니다.

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)

방법 3: 빠른 선택

빠른 선택 알고리즘은 실제로 빠른 선택과 유사하지만 각 이동마다 한 방향으로만 이동하면 된다는 점이 다릅니다.
시간 복잡도: O( n).

def qselect(A,k): 
  if len(A)<k:return A 
  pivot = A[-1] 
  right = [pivot] + [x for x in A[:-1] if x>=pivot] 
  rlen = len(right) 
  if rlen==k: 
    return right 
  if rlen>k: 
    return qselect(right, k) 
  else: 
    left = [x for x in A[:-1] if x<pivot] 
    return qselect(left, k-rlen) + right 
 
for i in range(1, 10): 
  print qselect([11,8,4,1,5,2,7,9], i)

최대 K 문제의 Python 버전과 관련된 더 많은 기사를 보려면 PHP 중국어 웹사이트를 참고하세요. !