Find the Running Median

  • + 0 comments

    c++ solution, i also modified this line: for (size_t i = 0; i < result.size(); i++) { cout << std::fixed << std::setprecision(1) << result[i]; if (i != result.size() - 1) { cout << "\n"; } }

    vector<double> runningMedian(vector<int> a) {
    vector<int> sortedvec;
    vector<double>result;
    sortedvec.reserve(a.size());
    result.reserve(a.size());
    sortedvec.push_back(a[0]);
    double d = a[0] * 1.0;
    result.push_back(d);
    int N = sortedvec.size();
    for (int i = 1; i < a.size(); ++i) {
        auto index = upper_bound(sortedvec.begin(), sortedvec.end(), a[i]);
        sortedvec.insert(index, a[i]);
        N = sortedvec.size();
        double median;
        if (N % 2 == 0) {
            int mid = N / 2;
            median = (sortedvec[mid] + sortedvec[mid - 1]) / 2.0;
        }
        else {
            median = sortedvec[N / 2] * 1.0;
        }
        result.push_back(median);
    		
    }
    return result;