数组排序问题

妖狐艹你老母 2022-05-15 20:17 430阅读 0赞

牛客网上有一道很典型的数组排序问题：先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉。然后再把这些数从小到大排序(同一个测试用例里可能会有多组数据，希望大家能正确处理)。

我的做法比较常规：先存储数组，然后去重，之后排序输出。编写代码：

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    int main(){
        int num;
        while(cin>>num){
            int array[num];
            for(int i=0;i<num;++i){
                cin >> array[i];
            }
            for(int i=0;i<num-1;++i){   //对于重复元素全部置“0”，因为“0”不在题目要求范围之类
                if(array[i]!=0){
                    for(int j=i+1;j<num;++j){
                        if(array[i]==array[j]){
                            array[j]=0;
                        } 
                    }
                }
            }
            sort(array,array+num);  //可以直接使用sort()函数
    /* 
            int temp;
            for(int i=0;i<num-1;++i){
                for(int j=i+1;j<num;++j){
                    if(array[i]>array[j]){
                        temp=array[i];
                        array[i]=array[j];
                        array[j]=temp;
                    }
                }
    */
            for(int i=0;i<num;++i){
                if(array[i]){         //去重时已经将重复元素置“0”，因此对于排序结果只输出非零元素即可
                      cout << array[i] << endl;
                }
            }
        }
        return 0;
    }

以上做法比较容易理解，但是执行过程稍微有点繁琐。在牛客网讨论贴吧中，有网友给出了另外一种简洁、经典的算法，代码如下：

链接：https://www.nowcoder.com/questionTerminal/3245215fffb84b7b81285493eae92ff0
    来源：牛客网
    
    #include <iostream>
    using namespace std;
    int main() {
        int N, n;
        while (cin >> N) {
            int a[1001] = { 0 };
            while (N--) {
                cin >> n;
                a[n] = 1;
            }
            for (int i = 0; i < 1001; i++)
                if (a[i])
                    cout << i << endl;
        }
        return 0;
    }

该算法直接以输入元素值作为数组下标，遍历所有元素即遍历数组下标，在这过程中相等元素作为下标给数组赋值时并没有影响，自然而然地过滤了重复元素，之后再按照已赋值数组元素筛选出输出下标值，不得不说，作者的构思很巧妙。