牛客周赛 Round 29

D-小红的中位数_牛客周赛 Round 29 (nowcoder.com)

错解(超时！！！)：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    vector<double> a(n);
    for (long long i = 0; i < n; i++)
        cin >> a[i];
    for (long long i = 0; i < n; i++)
    {

        double temp = a[i];
        a[i] = 0;
        vector<double> b(a);
        sort(b.begin(), b.end());
        if (n % 2 == 0)
            printf("%.1lf\n", b[n / 2]);
        else
            printf("%.1lf\n", (b[n / 2] + b[n / 2 + 1]) / 2);
        a[i] = temp;
    }
    return 0;
}

错误原因：

时间复杂度是O (n^2 log n)，其中n是vector的大小

[用一个vector去初始化另外一个vector的时间复杂度取决于vector的大小和元素类型。一般来说，这种操作的时间复杂度是线性的，也就是说，如果vector有n个元素，那么初始化另一个vector需要n次拷贝或移动操作]

正解：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    vector<long long> b(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b.begin(), b.end());
    for (int i = 1; i <= n; i++)
    {
        if (n & 1)
        {
            if (a[i] <= b[n / 2])
                printf("%.1lf\n", (b[n / 2 + 1] + b[n / 2 + 2]) * 1.0 / 2);
            else if (a[i] <= b[n / 2 + 1])
                printf("%.1lf\n", (b[n / 2] + b[n / 2 + 2]) * 1.0 / 2);
            else
                printf("%.1lf\n", (b[n / 2] + b[n / 2 + 1]) * 1.0 / 2);
        }
        else
        {
            if (a[i] <= b[n / 2])
                printf("%.1lf\n", b[n / 2 + 1] * 1.0);
            else
                printf("%.1lf\n", b[n / 2] * 1.0);
        }
    }
    return 0;
}

分析：

由储备知识可知，中位数的求法与数组长度有关，n为偶数则中位数=(a[n/2]+a[n/2+1])/2,n为奇数则中位数=a[(n+1)/2]。因此，得根据数组长度来分类讨论此题。

首先分析样例1

n为偶数时，删除元素后，数组长度为奇数。

对每种情况都分析发现，删除对应元素后的数组为，5 8 1；2 8 1；2 5 1；2 5 8

​ 对应的中位数为 5 2 2 5

因此，中位数只可能是2或5，归纳可知，原数组长度为偶数时，删除一个元素后的数组中位数只与中间两位有关

进一步分析，删除的元素小于等于中间前者数时，中位数为中间后者数，反之同理。

n为奇数时，删除元素后，数组长度为偶数。

对每种情况都分析发现，删除对应元素后的数组为：2 3；1 3；1 2

对应的中位数为：2.5 2 1.5

因此，原数组长度为奇数时，删除一个元素后的数组中位数可能与中间三位数有关

进一步分析，删除元素与中间三个数（依次设为a,b,c）比较，删除的那个元素小于等于a时，中位数=(b+c)/2；大于a且小于等于b时，中位数=(a+c)/2;大于b时，中位数=(a+b)/2；