数组去重排序

NVIDIA笔试2018-09-04思路

题目：数组去重排序

Example:

输入：
第一行：一个整数N
第二行：N个整数Ai
输出：
第一行：整数M，去重后的数量
第二行：M个整数按顺序排列

样例输入

5
2 1 2 3 4

样例输出

4
1 2 3 4

解析

输入
输入数据共2行，第一行输入测试数据个数n，第二行输入这n个整数，整数之间可能有重复，整数之间可能有若干个空格。
n <= 105，所有的整数不超过104。
输出
去重后的数量
输出为1行，是这n个数去重后从小到大的排序。

代码（C++）

#include<iostream>
using namespace std;
void Qsort(int a[], int low, int high)
{
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[first];
    
    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            --last;
        }
        
        a[first] = a[last];
        
        while(first < last && a[first] <= key)
        {
            ++first;
        }
        
        a[last] = a[first];
    }
    a[first] = key;
    Qsort(a, low, first-1);
    Qsort(a, first+1, high);
}

int main()
{
    int n;
    cin>>n;
    int m=1;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    Qsort(a,0,n-1);
    

    for(int i=1;i<n;i++)
    {
        if(a[i]!=a[i-1])
        {
            m++;
        }
    }
    cout<<m<<endl;
    cout<<a[0]<<" ";
    for(int i=1;i<n;i++)
    {
        if(a[i]!=a[i-1])
        {
            cout<<a[i]<<" ";
        }
    }
    return 0;
}