[LeetCode]: 295. 데이터 흐름 의 중위 수
질문 설명:
중위 수 는 서열 표 중간의 수 이다.목록 길이 가 짝수 라면, 중위 수 는 중간 두 수의 평균 값 이다.
예컨대
[2, 3, 4] 의 중위 수 는 3 이다.
[2, 3] 의 중위 수 는 (2 + 3) / 2 = 2.5 이다.
다음 두 가지 조작 을 지원 하 는 데이터 구 조 를 설계 합 니 다.
[제목 링크] (https://leetcode-cn.com/problems/find-median-from-data-stream/
예시 1
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2
생각:
이 문제 의 가장 중요 한 부분 은 우리 가 데 이 터 를 두 부분 으로 골 고루 나 누 어야 한 다 는 것 이다. 앞부분 의 모든 데 이 터 는 뒷부분 보다 작다. 그러면 우 리 는 시간 복잡 도
O(1) 에 있 을 수 있다.배열 의 중위 수 를 찾 습 니 다. 이 문 제 는 가장 많은 더미 와 최소 더미 로 이 목적 을 달성 하 는 것 을 고려 합 니 다. 데이터 가 두 부분 으로 고 르 게 나 뉘 도록 하기 위해 서 두 더미 의 숫자 차 이 는 1 을 초과 할 수 없습니다. 따라서 우 리 는 데이터 의 총 수량 이 짝수 일 때 새 데 이 터 를 최소 더미 에 삽입 합 니 다. 그렇지 않 으 면 최대 더미 에 삽입 합 니 다.그 밖 에 가장 많은 데 이 터 는 최소 더미 의 데이터 보다 작 아야 합 니 다. 데 이 터 를 최소 더미 에 삽입 할 때 먼저 최대 더미 에 삽입 한 다음 에 가장 많은 최대 치 를 꺼 내 최소 더미 에 삽입 하면 최소 더미 의 모든 숫자 가 가장 많은 것 보다 크다 는 것 을 보증 할 수 있 습 니 다. 또한 데이터 분포 가 균일 합 니 다. 코드 는 다음 과 같 습 니 다.
전체 코드:
public class MedianFinder {
// count ，
private int count = 0;
private PriorityQueue minHeap;
private PriorityQueue maxHeap;
public MedianFinder() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>((a,b) -> {return b-a;});
}
public void addNum(int num) {
if (count % 2 == 0) {
maxHeap.offer(num);
int tmp = maxHeap.poll();
minHeap.offer(tmp);
}else {
minHeap.offer(num);
int tmp = minHeap.poll();
maxHeap.offer(tmp);
}
count++;
}
public double findMedian() {
if(count %2 == 0){
return new Double((minHeap.peek() + maxHeap.peek())) / 2;
}else{
return new Double(minHeap.peek());
}
}
}
GitHub 링크 추가
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
