《剑指offer》：排序

ゞ浴缸里的玫瑰 2023-02-15 10:09 6阅读 0赞

**一、数据流中的中位数**

**题目描述：**如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

**解题思路：**这里考虑到是从数据流中获取，那么数据就是不断更新的。使用大顶堆来存放排序后前半部分（小的数），使用小顶堆来存放排序后的后半部分（大的数）。其中需要注意的是以下堆的几个操作：

1.  将元素入堆：m.push\_back(x);
2.  向堆中添加新的元素作为叶子节点：push\_heap(m.begin(),m.end(),less<int>())
3.  堆顶元素出堆：
    
    1.  pop\_heap(m.begin(),m.end(),less<int>())
    2.  m.pop\_back()

class Solution {
    private:
        vector<int>max;
        vector<int>min;
    public:
        void Insert(int num)
        {
            int size=max.size()+min.size(); //统计整个数据的长度
            if((size&1)==0) //这里先判断奇偶性，如果是奇数个数字，则遍历大顶堆，统计前半部分数组。
            {
                if(max.size()>0&&num<max[0])
                {
                    max.push_back(num);
                    push_heap(max.begin(),max.end(),less<int>()); //添加数据流中的新元素，作新的叶节点
                    num=max[0]; //获取堆顶元素以便放到后半部分数据组成的小顶堆中
                    pop_heap(max.begin(),max.end(),less<int>()); //堆顶元素出堆
                    max.pop_back();
                }
                //将大顶堆中的堆顶元素放到小顶堆中以便平衡元素
                min.push_back(num);
                push_heap(min.begin(),min.end(),greater<int>());
                
            }
            else
            {
                if(min.size()>0&&num>min[0])
                {
                    min.push_back(num);
                    push_heap(min.begin(),min.end(),greater<int>()); //添加数据流中的新元素
                    num=min[0]; //获取堆顶元素以便放到前半部分数据组成的大顶堆中
                    pop_heap(min.begin(), min.end(),greater<int>()); //堆顶元素出堆
                    min.pop_back();
                }
                //将小顶堆中的堆顶元素放到大顶堆中以便平衡元素
                max.push_back(num);
                push_heap(max.begin(), max.end(),less<int>()); //堆顶元素出堆
            }
        }
        double GetMedian()
        {
            int size=max.size()+min.size();
            if(size<=0) return 0;
            if((size&1)==0) //判断奇偶性
                return (max[0]+min[0])/2.0;
            else
                return min[0];
        }
    
    };

**二、最小的K个数**

**题目描述**：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

**解题思路**：

*  方法一：使用sort排一遍序，如果没有时间复杂度的要求的话，可以OK没问题。

class Solution {
    public:
        vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
             
             
            vector<int> v;
            if(k>input.size())
                return v;
            sort(input.begin(),input.end());
            for(int i=0;i<k;i++)
                v.push_back(input[i]);
            return v;      
        }
    };

*  方法二：使用快排的思想，通过函数计算，使k以前的数都小于k，k之后的数都大于k，这样，最终只需要取前k个数即可。时间复杂度o(n)。

#include <iostream>
    #include<vector>
    using namespace std;
    int each_sort(vector<int>&a,int i,int j)
    {
        int tmp=a[i];
        if(i<j)
        {
            while(i<j&&a[j]>tmp) j--;
            if(i<j) a[i]=a[j];
            while(i<j&&a[i]<tmp) i++;
            if(i<j) a[j]=a[i];
        }
        a[i]=tmp;
        return i;
    }
    void kp_sort(vector<int>&Array,int Begin,int End)
    {
       if(Begin<End)
       {
           int tmp=each_sort(Array,Begin,End); //查找每次分配完成的中点
           kp_sort(Array,Begin,tmp-1); //左边
           kp_sort(Array,tmp+1,End); //右边
       }
    }
    int main()
    {
        vector<int>arr{1,3,2,4,6,5,7,9,13,12};
        int k;
        cin>>k;
        kp_sort(arr,0,arr.size()-1);
        for(int j=0;j<k;j++)
            cout<<arr[j]<<',';
        return 0;
    }