华为机试题 -- 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤1000），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

Input Param

n 输入随机数的个数

inputArray n个随机整数组成的数组

Return Value

OutputArray 输出处理后的随机整数

注：测试用例保证输入参数的正确性，答题者无需验证。测试用例不止一组。

输入描述:

输入多行，先输入随机整数的个数，再输入相应个数的整数

输出描述:

返回多行，处理后的结果

输入例子:

输出例子:

10
15
20
32
40
67
89
300
400

思路一：

最笨的办法，先去重，可以利用开辟另一个数组，然后再排序，不过这样复杂度太高，估计爆了



思路二：

利用关联容器set来做，set 不允许有重复值，而且是有序的。操作简单，

#include <iostream>
#include <set>
using namespace std;
int main()
{
    int n;
    while(cin >> n)
    {
           set <int> arr;
        int tem;
        for ( int i = 0; i <　n; i++)
        {
            cin >> tem;
            arr.insert(tem);
        }
        for (auto j : arr)
        {
            cout << j << endl;
        }       
    }   
    return 0;
}

注释

1.set容器

C++Primer第五版11章关联容器—— PP373
关联容器支持高效的关键字查找和访问。

set是一个要求不重复关键字，有序存储的集合。
set的两个重要属性：
a. set中每个元素只包含一个关键字
正好适合本题的“去重”要求
声明格式：

#include<set>
set<int>arr;

b. set按关键字有序（从小到大）保存元素
对应本题的“排序”要求
声明格式：

arr.insert(input);

2.范围for语句

C++Primer第五版使用基于范围的for语句—— PP82
如果想对string对象中的每个字符做点什么操作，目前最好的办法是使用C++11新标准提供的一种语句，范围for（range for）语句。这种语句遍历给定序列中的每个元素并对序列中的每个值执行某种操作，其语法形式是：

for(declaration: expression)
statement

其中，expression部分是一个对象，用于表示一个序列。
declaration部分负责定义一个变量，该变量将被用于访问序列的基础元素。每次迭代，declaration部分的变量会被初始化为expression部分的下一个元素值。

string str(“some”);
for (auto c : str) //对于str的每个字符
cout << c << endl; //输出当前字符，后面紧跟一个换行符

通过使用auto关键字让编译器决定变量c的类型，这里c是char，每次迭代，str的下一个字符被拷贝给c，因此该循环可以读作”对于字符串str中的每个字符c“执行某某操作。


思路三：


牛客网看的，感觉很好，

#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;}