剑指offer-刷题笔记-中难题-JZ41 数据流中的中位数

剑指offer-刷题笔记-中难题-JZ41 数据流中的中位数

版本1

使用外部交换排序方法排序不断排序数组

class Solution {
public:
     //交换
    void swap(int &a,int &b)
    {
        int temp;
        temp = a;
        a = b;
        b = temp;
    }
    
    //交换排序-从小到大排序
    void swapSort(vector<int> &input)
    {
        for(int i = 0;i < input.size(); i++)
        {
            for(int j = i+1;j < input.size(); j++)
            {
                if(input[j] < input[i])
                {
                     swap(input[i],input[j]);
                }
            }
        }
    }
    vector<int>input;
    void Insert(int num) {
       input.push_back(num);
       swapSort(input);
    }
    double GetMedian() { 
       
       double res;
       if(input.size() % 2 == 1)
       {
           res =  input[input.size() / 2] * 1.0;
       }else if (input.size() % 2 == 0)
       {
           res = (input[input.size() / 2] + input[(input.size() / 2)-1]) * 0.5;   
       }
        return res;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

版本2

利用数据读入的时候排序

class Solution {
public:
  
    vector<int>input;
    void Insert(int num) {
        if(input.empty())
        {
            //input中没有数据，直接加入
            input.push_back(num);
        }else{
            //遍历排序，并插入
            int i = 0;
            for(;i < input.size();i++)
            {
                if(num < input[i])
                {
                    break;
                }
            }
            input.insert(input.begin()+i, num);
        }
    }
    double GetMedian() { 
       
       double res;
       int n = input.size();
       if( n % 2 == 1)
       {
           res =  input[n / 2] * 1.0;
       }else if (n % 2 == 0)
       {
           res = (input[n / 2] + input[(n / 2)-1]) * 0.5;   
       }
        return res;
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

版本3

利用大顶堆和小顶堆的特性

class Solution {
public:
  
    //优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，
    //其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂
    //度都是O(log2n)O(log_2n)O(log 
    //n)，而每次取出堆顶元素都是直接取出。

 //维护两个堆，取两个堆顶部即可
    void Insert(int num)
    {
        //先加入较小部分
        min.push(num);
        //将较小部分的最大值取出，送入到较大部分
        max.push(min.top());
        min.pop();
        //平衡两个堆的数量
        if(min.size() < max.size())
        {
            min.push(max.top());
            max.pop();
        }
        
    }
    
    double GetMedian() { 
        //奇数个
        if(min.size() > max.size())
            return (double)min.top();
        //偶数个
        else
            return (double)(min.top() + max.top()) / 2;
    }
private:
    //大顶堆,元素值较小
    priority_queue<int>min;
    //小顶堆，元素值都比大顶堆大
    priority_queue<int,vector<int>,greater<int>> max;
   
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40