[python]Hip双優先級キュー[3ステップ]
8877 ワード
問題の説明
デュアル・ユーティリティ・プリアンブル・キューとは、次の演算が可能なデータ構造です.
コマンド受信タワー(高さ)Iのデジタルキューに指定した数字を挿入します.D 1キューから最値を削除します.D-1キューから最大値を削除します.
パラメータとして2つの優先順位キューで実行する演算操作を指定した場合、すべての演算を処理した後、キューが空の場合[0,0]空でない場合、「最値、最上昇値」を返すソルバを実装します.
せいげんじょうけん
operationsは、長さが1または1000000未満の文字列配列です.
operationsの要素は、キューが実行する演算を表します.
要素はコマンドデータ形式で与えられます.最大値/最大値を削除する操作で複数の最大値/最大値がある場合は、1つだけ削除します.
空のキューからデータを削除する必要がある場合は、この操作は無視されます.
I/O例
operationsreturn["I 16","D 1"][0,0]["I 7","I 5","I -5","D -1"][7,5]
I/O例説明
16を挿入すると、最大値が削除されます.[0,0]を返します.空ですから.
7、5、および-5を挿入して、最大値を削除します.最大値7、最小値5を返します.
Java解釈
import heapq
def solution(operations):
answer = []
heap = [] # 힙 생성
for data in operations:
# 연산이 "I"일 경우 공백 뒤의 숫자를 heap에 넣음
if data[0] == "I":
heapq.heappush(heap, int(data[2:]))
# 연산이 "D"일 경우
else:
if len(heap) == 0:
pass
# 공백 뒤가 "-"일 경우 최소힙을 제거
elif data[2] == "-":
heapq.heappop(heap)
# 공백 뒤가 아무것도 아닌 경우
else:
# 힙에서 가장 큰 수를 제외하고 다시 힙에 넣음
heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)
if heap:
answer.append(max(heap))
answer.append(min(heap))
else:
answer.append(0)
answer.append(0)
return answer
import heapq
def solution(operations):
min_heap = []
for value in operations:
order, data = value.split()
data = int(data)
# 최댓값 삭제
if order == "D" and data == 1:
if min_heap:
max_value = max(min_heap)
min_heap.remove(max_value)
# 최솟값 삭제
elif order == "D" and data == -1:
if min_heap:
heapq.heappop(min_heap)
# 큐 데이터 삽입
else:
heapq.heappush(min_heap, data)
# heap이 비어있는 경우
if not min_heap:
return [0, 0]
return max(min_heap), min_heap[0]
Reference
この問題について([python]Hip双優先級キュー[3ステップ]), 我々は、より多くの情報をここで見つけました https://velog.io/@dmsql698/Python-힙이중우선순위큐3단계テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol