P1059 [NOIP2006 普及组] 明明的随机数 题解

· · 题解

题解区的去重函数竟是一笔带过……

排序函数sort

包括使用方法和底层原理的介绍，知道的可以绕道。

首先先介绍一个人人熟知的排序函数：sort。

需使用algorithm头文件

sort(开始指针，结束指针，比较方式)

其中，开始指针和结束指针为必填项，比较方式为选填项。如果不填，则默认为从小到大排序。

另外，如果使用结构体，那么比较方式为必填项，一些包含精度问题的排序也建议写上。

好的，你已经了解了排序函数的用法，那么它的底层原理最好也了解下。

首先，快排先选择一个量为基准值，一般用第一个数。

然后，按基准值分为左右两边，（以从小到大为例）左边是比基准值小的，右边是比基准值大的。这里不用新开数组，我们发现，一个值是不合法的，那么另一边也一定有一个不合法的，交换即可。

然后，分别递归左右两边。

以上方法叫一轮快排。（便于分析复杂度）

模版代码（不是本题！！！）：

#include<bits/stdc++.h>
using namespace std;
int n,a[10005],b[10005]; 
void qsort(int l,int r){
    int i=l,j=r,mid=a[(l+r)>>1];
    while(i<=j){
        while(a[i]<mid)i++;
        while(a[j]>mid)j--;
        if(i<=j){
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if(l<j)qsort(l,j);
    if(i<r)qsort(i,r);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    qsort(1,n);
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

快排的时间复杂度比较玄学，可以如下分析：

一轮快排的时间复杂度为 O(n)，所以整个快排的时间复杂度为 O(n\times 快排轮数)，因为快排每次将数列分为左右两部分分别递归，我们只要考虑递归多少轮即可。如果基准值刚好将数列分为左右两边，那么就会递归 log_2n 轮。如果基准值是最值，那么会递归 n 轮。综上所述：

平均时间复杂度：O(nlogn)
最好时间复杂度：O(nlogn)
最坏时间复杂度：O(n^2)
稳定性：不稳定

注：快排可以使用随机打乱以避免最坏情况的出现。

去重函数unique

去重函数必须和快排一起使用，因为，去重函数的底层原理是比较相邻两个数，如果相同，就把其中一个扔到后面。继续比较。最后返回最后一个互异元素的地址。所以，如果不排序，去重函数就无法完成去重。

使用方法也很简单，unique(开始，结束)即可使用。

最短代码挑战&解释代码

先放代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[1005]={1};
int main(){
    for(int i=0;i<=a[0];i++)cin>>a[i];
    sort(a+1,a+a[0]+1);
    a[0]=unique(a+1,a+a[0]+1)-a-1;
    for(int i=0;i<=a[0];i++)cout<<a[i]<<((i==0)?"\n":" ");
}

至此，本篇题解结束，不过还是有必要解释一下代码

题解区里原有的最短代码是 19 行，而这里我写的是 9 行。

原本用正常马蜂（带压行）写出来之后是 11 行，我一咬牙，将它压进 9 行。

首先，我们要利用可以利用的空间来存储。这里的第一个空位（下标为零）刚好就可以利用，来代替数组长度，真正元素的下标从一开始。

我们将下标为零元素的值设为 1，这样程序就会先读入一个数，即 a_0，然后就会读入 a_0 个数，巧不巧妙？（行数-1）

然后，我们在将 a_0 用于存储去重后的元素个数，这样直接输出即可。不过，题目中要求元素个数要打回车，所以加个三目运算符判断一下即可，就省掉了单独输出的一行。（行数-1）

至此，本篇成为目前最短代码，统计截止至2024.9.30。