Running Median

Running Median

https://ac.nowcoder.com/acm/problem/50940

题意:输出数组图片说明 的中位数
懵逼的题解:每次数组图片说明 图片说明 排序...
我不知道为什么这个能过,
时间复杂度:图片说明
我怎么算这个时间复杂度也会炸的呀.......

//ac code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int p;
    cin>>p;
    while(p--)
    {
        int t,m;
        int ans=0;
        cin>>t>>m;
        int a[m+5];
        cout<<t<<" "<<m/2+1<<'\n';
        for(int i=0;i<m;i++) cin>>a[i];
        for(int i=0;i<m;i++)
        {
            if((i+1)%2!=0)
            {
                sort(a,a+i+1);
                if(ans==0) cout<<a[i/2];
                else cout<<" "<<a[i/2];
                ans++;
                if(ans==10)
                {
                    ans=0;
                    cout<<'\n';
                }
            }
        }
        if(p!=0)
            cout<<'\n';
    }
    return 0;
}

正常的题解:建立最大堆,最小堆(可以直接写优先队列,不用手动建堆)
把每次输入的元素压入最大堆和最小堆中,然后进行两个堆的调整,如果两个堆的堆顶值不同,那么连个堆堆顶值全部弹出,然后再交换压入,最后可以达到的效果是
大根堆存储的是数组图片说明
小根堆存储的是数组图片说明
其中图片说明
以上数字为调整后的数字大小,只用作举例说明,并且大根堆小根堆的数组长度相同,而且此处假设原数组为 图片说明
堆是什么呢 https://baike.baidu.com/item/%E5%A0%86/20606834?fr=aladdin ---来自百度百科
时间复杂度:图片说明
正常一点可以过的时间复杂的

#include<bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while(T--) {
     priority_queue<int,vector<int>, greater<int> > que_1; //小顶堆
priority_queue<int> que_2;
        int kk, n, x;
        cin >> kk >> n;
        cout << kk << ' ' << (n+1)/2 << endl;
        for(int i = 1; i <= n; i++) {
            cin >> x;
            que_1.push(x);
            que_2.push(x);
            if(i%2==0)
                continue;
            while(que_1.top() != que_2.top()) {
                int a = que_1.top();
                int b = que_2.top();
                que_1.pop(), que_2.pop();
                que_1.push(b);
                que_2.push(a);
            }
            cout << que_2.top() << ' ';
            if(((i+1)/2)%10 == 0)
                cout << "\n";
            else if((n%2==1&&i==n) || (n%2==0&&i==n-1))
                cout << "\n";
        }

    }
return 0;
}

上面的第一个题解更新之前能过,现在数据已经更新

全部评论
数据已更新 欢迎再试
点赞 回复 分享
发布于 2020-04-08 18:44

相关推荐

10-05 23:02
东北大学 Java
我说句实话啊:那时候看三个月培训班视频,随便做个项目背点八股,都能说3 40w是侮辱价
点赞 评论 收藏
分享
和蔼:在竞争中脱颖而出,厉害! 但是有一个小问题:谁问你了?😡我的意思是,谁在意?我告诉你,根本没人问你,在我们之中0人问了你,我把所有问你的人都请来 party 了,到场人数是0个人,誰问你了?WHO ASKED?谁问汝矣?誰があなたに聞きましたか?누가 물어봤어?我爬上了珠穆朗玛峰也没找到谁问你了,我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒,在找到谁问你之前我连癌症的解药都发明了出来,我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务