题解 | #售价的中位数#

知识点

模拟，排序

思路

每次在price中询问到第i个点，我们就将price[0~i-1]排序（注意数组下标从0开始）

若i+1为奇数，则说明当前的中位数是由两位数的平均值得来。

若i+1为偶数，则说明当前的中位数由区间[0,i]中间那一位数得来

初步判断算法时间复杂度为O(nLOGn),因为每次排序，只有第i位是变的，前i-1位已经有序。不过在此题中，使用sort也能通过，可能是数据范围比较小。

此外，可以考虑使用set来维护有序性，每次插入一个值的时间复杂度为LOGn

代码c++

public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @return double浮点型vector
     */
    vector<double> findMedianPrice(vector<int>& prices) {
        // write code here
        vector<double>ans;
        for(int i=0;i<prices.size();i++)
        {   sort(prices.begin(),prices.begin()+i+1);
            if(i%2==0)
            {
                ans.push_back(prices[i/2]);
            }
            else {
            ans.push_back((double)(prices[i/2]+prices[i/2+1])/2);
            }
        }
        return ans;
    }
};