LeetCode295——Find Median from Data Stream
2092 단어 leetcode
전제는 Ordered List입니다.
그러나 삽입, 즉 addNum 작업은 순서가 없을 수 있습니다.
시퀀스 정렬을 시도한 후에 되돌아오는 방법은 시간이 초과되었습니다.생각해보니까 천진하다. 코드:
class MedianFinder {
private:
vectornums;
public:
// Adds a number into the data structure.
void addNum(int num) {
nums.push_back(num);
sort(nums.begin(),nums.end());
}
// Returns the median of current data stream
double findMedian() {
if(nums.size()%2==0)
{
return (nums[nums.size()/2]+nums[nums.size()/2-1])/2.0;
}
else
{
return nums[nums.size()/2];
}
}
}; 이 문제의 관건은 두 개의 무더기, 한 개의 큰 무더기, 한 개의 작은 무더기를 유지하는 데 있다. 이렇게 하면 삽입할 때 이미 질서가 보장된다.
큰 지붕더미에 대해 지붕은 틀림없이 더미 중 가장 큰 값이다.
작은 지붕더미에 대해 지붕은 틀림없이 더미 중 가장 작은 값이다.
지금 우리는 질서정연한 서열을 가설하고 이 서열을 반으로 나눈다. 왼쪽 반은 비교적 소수이고 오른쪽 반은 비교적 큰 수이다.
우리는 비교적 작은 수를 큰 무더기로 저장하고, 비교적 큰 수는 작은 무더기로 저장한다.
그러면 큰 무더기의 뿌리는 반드시 소수 안의 최대수이고 작은 무더기의 뿌리는 반드시 큰 수 안의 최소수이며 질서 서열 중의 중간의 두 개수이다.
우리는 삽입 과정 중, 시종 크기 무더기의 크기 차이가 초과하지 않도록 보증한다.1
삽입이 완료되면 다음이 수행됩니다.
큰 무더기의 크기 = 작은 무더기의 크기가 되돌아오기(maxHeap.top () +minHeap.top() )/2.0
큰 무더기의 크기 > 작은 무더기의 크기는 maxHeap로 바로 돌아갑니다.top()
그렇지 않으면 MinHeap로 바로 돌아갑니다.top()
코드:
class MedianFinder {
private:
priority_queue ,less> maxHeap; //
priority_queue,greater> minHeap; //
public:
// Adds a number into the data structure.
void addNum(int num) {
maxHeap.push(num);//
int t = maxHeap.top(); //
maxHeap.pop();
minHeap.push(t);//
int maxLen = maxHeap.size();
int minLen = minHeap.size();
if (minLen - maxLen > 0)
{
int t = minHeap.top();
maxHeap.push(t);
minHeap.pop();
}
}
// Returns the median of current data stream
double findMedian() {
if (maxHeap.size() > minHeap.size())
return maxHeap.top()*1.0;
else if (maxHeap.size() < minHeap.size())
return minHeap.top()*1.0;
else
return (minHeap.top() + maxHeap.top()) / 2.0;
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
