洛谷P4305题解

传送锚点

摸鱼环节

[JLOI2011] 不重复数字

题目描述

给定 \(n\) 个数，要求把其中重复的去掉，只保留第一次出现的数。

输入格式

本题有多组数据。

第一行一个整数 \(T\)，表示数据组数。

对于每组数据：

第一行一个整数 \(n\)。

第二行 \(n\) 个数，表示给定的数。

输出格式

对于每组数据，输出一行，为去重后剩下的数，两个数之间用一个空格隔开。

样例 #1

样例输入 #1

2
11
1 2 18 3 3 19 2 3 6 5 4
6
1 2 3 4 5 6

样例输出 #1

1 2 18 3 19 6 5 4
1 2 3 4 5 6

提示

对于 \(30\%\) 的数据，\(n \le 100\)，给出的数 \(\in [0, 100]\)。

对于 \(60\%\) 的数据，\(n \le 10^4\)，给出的数 \(\in [0, 10^4]\)。

对于 \(100\%\) 的数据，\(1 \le T\le 50\)，\(1 \le n \le 5 \times 10^4\)，给出的数在 \(32\) 位有符号整数范围内。

这回真来水题解了这次我来打打基础。众所周知，基础很重要。

正片开始

考虑用结构体维护原始下标，数值，是否为第一个出现的数这三个信息。

1. 首先将原序列按数值大小进行排序，将重复的标记。
2. 再将原序列按初始下标排序，对于没有被标记的数，直接输出。

code：

struct node
{
    int x,num,f=0;
}a[N];
bool cmp(node q,node p)
{
    if(q.num==p.num) return q.x>p.x;//相等的数将原始下标大的放前面
    else return q.num<p.num;
}
bool cmp2(node q,node p){return q.x<p.x;}

是的，没错，结束了。

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
int t;
struct node
{
    int x,num,f=0;
}a[N];
bool cmp(node q,node p)
{
    if(q.num==p.num) return q.x>p.x;
    else return q.num<p.num;
}
bool cmp2(node q,node p){return q.x<p.x;}
int main()
{
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof(a));
        int n;cin>>n;
        for(int i=1;i<=n;i++){cin>>a[i].num;a[i].x=i;}
        sort(a+1,a+n+1,cmp);
        for(int i=1;i<=n;i++){if(a[i].num==a[i+1].num) a[i].f=1;}
        sort(a+1,a+n+1,cmp2);
        for(int i=1;i<=n;i++)
        {
            if(a[i].f) continue;
            else cout<<a[i].num<<" ";
        }
        cout<<endl;
    }
	return 0;
}

完结收工！！！！！

个人主页

看完点赞，养成习惯

\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)