[검 지 Offer] 데이터 흐름 의 중위 수

제목 설명
어떻게 데이터 흐름 중의 중위 수 를 얻 습 니까?데이터 흐름 에서 홀수 수 수 치 를 읽 으 면 중위 수 는 모든 수치 가 정렬 된 후에 중간 에 있 는 수치 입 니 다.데이터 흐름 에서 짝수 수 수 치 를 읽 으 면 중위 수 는 모든 수치 가 정렬 된 후 중간 두 수의 평균 값 이다.
 
데이터 흐름 에 대응 하 는 것 은 바로 온라인 알고리즘 입 니 다. 전형 적 인 문 제 는 1 억 개의 숫자 에서 가장 큰 100 개의 수 를 찾 는 것 입 니 다. 이것 은 응용 문제 입 니 다. 가장 큰 100 개의 수 를 찾 으 면 우 리 는 크기 가 100 인 최소 화 더 미 를 만 듭 니 다. 모든 원 소 는 쌓 인 요소 와 비교 합 니 다. 쌓 인 요 소 는 현재 100 대 에서 가장 작은 숫자 이기 때 문 입 니 다.온 원소 가 이 원소 보다 크 면 원래 의 쌓 인 지붕 을 교체 합 니 다.
그러면 이 문제 에 대해 서 는 요?단순히 모든 요 소 를 한 배열 에 넣 으 면 중위 수 를 찾 을 때마다 가장 빠 르 고 O (n) 가 필요 하 며 종합 하면 O (n ^ 2) 의 복잡 도 입 니 다.우 리 는 위의 예 에서 의 아 이 디 어 를 이용 하여 현재 n / 2 작은 요 소 를 최대 더미 로 유지 할 수 있 습 니 다. 그러면 매번 중위 수 를 찾 을 때마다 더미 꼭대기 만 꺼 내 면 됩 니 다.그러나 한 가지 문제 가 있 습 니 다. 데 이 터 는 동태 적 으로 증가 해 야 합 니 다. 예전 에 교 체 된 요소 가 요소 의 증가 에 따라 다시 달 려 올 수 있 습 니 다. 그래서 우 리 는 단순히 위 문제 처럼 요 소 를 버 릴 수 없습니다. 우 리 는 최소 화 된 더미 로 n / 2 큰 요 소 를 저장 할 수 있 습 니 다.

 1 #include <bits/stdc++.h>

 2 using namespace std;

 3 

 4 class Solution {

 5     private:

 6         vector<int> min; //                 

 7         vector<int> max; //                 

 8     public:

 9         void Insert(int num) {

10             if(((min.size()+max.size()) & 1) == 0) {  //        ，          

11                 if(max.size() > 0 && num < max[0]) {

12                     max.push_back(num);

13                     push_heap(max.begin(), max.end(), less<int>());

14                     num=max[0];

15                     pop_heap(max.begin(), max.end(), less<int>());

16                     max.pop_back();

17                 }

18                 min.push_back(num); //                

19                 push_heap(min.begin(), min.end(), greater<int>());

20             } else {

21                 if(min.size() > 0 && num > min[0]) {   //        ，          

22                     min.push_back(num);

23                     push_heap(min.begin(), min.end(), greater<int>());

24                     num=min[0];

25                     pop_heap(min.begin(), min.end(), greater<int>());

26                     min.pop_back(); 

27                 }

28                 max.push_back(num); //                

29                 push_heap(max.begin(), max.end(), less<int>());

30             }

31         }

32 

33         double GetMedian() { 

34             int size=min.size() + max.size();

35             if(size==0) return -1;

36             double median = 0;

37             if((size&1) != 0) {

38                 median = (double) min[0];

39             } else {

40                 median = (double) (max[0] + min[0]) / 2;

41             }

42             return median;

43         }

44 };

45 

46 int main() {

47     Solution s;

48     vector<int> v{5,2,3,4,1,6,7,0,8};

49     for (int i = 0; i < v.size(); ++i) {

50         s.Insert(v[i]);

51         cout << s.GetMedian() << endl;

52     }

53     return 0;

54 }

멀 티 셋 을 사용 하여 프로 그래 밍 을 간소화 할 수도 있 고, lintcode 에 도 원제 가 있다.
http://www.lintcode.com/en/problem/data-stream-median/

 1 class Solution {

 2 public:

 3     /**

 4      * @param nums: A list of integers.

 5      * @return: The median of numbers

 6      */

 7     vector<int> medianII(vector<int> &nums) {

 8         // write your code here

 9         multiset<int> left, right;

10         vector<int> res;

11         bool flag = true;

12         for (int n : nums) {

13             int tmp = n;

14             if (flag) {

15                 if (!right.empty() && n > *right.begin()) {

16                     right.insert(n);

17                     tmp = *right.begin();

18                     right.erase(right.find(tmp));

19                 }

20                 left.insert(tmp);

21             } else {

22                 if (!left.empty() && n < *left.rbegin()) {

23                     left.insert(n);

24                     tmp = *left.rbegin();

25                     left.erase(left.find(tmp));

26                 }

27                 right.insert(tmp);

28             }

29             flag = !flag;

30             res.push_back(*left.rbegin());

31         }

32         return res;

33     }

34 };

또 하 나 는 미끄럼 창의 중위 수 를 구 하 는 것 이지 사실은 같은 사상 에 기초 한 것 이다.다만 창 이 미 끄 러 질 때 요소 가 창 에서 미 끄 러 지기 때문에 새로운 요 소 를 삽입 하기 전에 미 끄 러 지 는 요 소 를 삭제 해 야 합 니 다.
http://www.lintcode.com/en/problem/sliding-window-median/

 1 class Solution {

 2 public:

 3     /**

 4      * @param nums: A list of integers.

 5      * @return: The median of the element inside the window at each moving

 6      */

 7     vector<int> medianSlidingWindow(vector<int> &nums, int k) {

 8         // write your code here

 9         vector<int> res;

10         if (k > nums.size() || k == 0) return res;

11         multiset<int> left, right;

12         //init heaps by first kth elements in nums

13         for (int i = 0; i < k; ++i) {

14             left.insert(nums[i]);

15         }

16         while (left.size() > (k + 1) / 2) {

17             right.insert(*left.rbegin());

18             left.erase(left.find(*left.rbegin()));

19         }

20         res.push_back(*left.rbegin());

21         //slide window

22         for (int i = k; i < nums.size(); ++i) {

23             //delete the leftmost element in window from heaps

24             if (nums[i-k] > res.back()) right.erase(right.find(nums[i-k]));

25             else left.erase(left.find(nums[i-k]));

26             //insert new element into heaps

27             if (!left.empty() && nums[i] <= *left.rbegin()) left.insert(nums[i]);

28             else right.insert(nums[i]);

29             //adjust heaps so that the left heap contains (k + 1) / 2 elements

30             while (left.size() < (k + 1) / 2) {

31                 left.insert(*right.begin());

32                 right.erase(right.begin());

33             }

34             while (left.size() > (k + 1) / 2) {

35                 right.insert(*left.rbegin());

36                 left.erase(left.find(*left.rbegin()));

37             }

38             res.push_back(*left.rbegin());

39         }

40         return res;

41     }

42 };