【 더미 】 A013LC_데이터 흐름 의 중위 수 (데이터 양의 패 리 티 분석 + 데이터 흐름 의 좌우 부분 으로 추상 화)
[2, 3, 4] 의 중위 수 는 3 이다 [2, 3] 의 중위 수 는 (2 + 3) / 2 = 2.5 이다.
다음 두 가지 조작 을 지원 하 는 데이터 구 조 를 설계 합 니 다.
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
진급: 만약 데이터 흐름 중의 모든 정수 가 0 에서 100 범위 내 에 있다 면 당신 은 어떻게 당신 의 알고리즘 을 최적화 할 것 입 니까?만약 데이터 흐름 중 99% 의 정수 가 0 에서 100 범위 내 에 있다 면 당신 은 어떻게 당신 의 알고리즘 을 최적화 할 것 입 니까?
방법 1: 더미
사고의 방향
폭력 서열 만 생각 하고 다른 사람의 생각 을 참고 하 라. 데 이 터 를 두 부분 으로 나 누 면 중위 수 는
( maxVal + minVal) / 2 이 고 그 다음은 데이터 흐름 의 수량 에 대한 패 리 티 를 토론 하 는 것 이다.class MedianFinder {
Queue<Integer> minQ, maxQ;
int tot;
public MedianFinder() {
minQ=new PriorityQueue<>();
maxQ=new PriorityQueue<>(Collections.reverseOrder());
}
public void addNum(int num) {
maxQ.add(num);
minQ.add(maxQ.poll());
if (minQ.size() > maxQ.size()) {
maxQ.add(minQ.poll());
}
tot++;
}
public double findMedian() {
return (tot&1)==1 ? maxQ.peek() : (minQ.peek()+maxQ.peek())*0.5;
}
}
복잡 도 분석
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
