[编程题]明明的随机数

绝地灬酷狼 2022-07-14 11:38 155阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

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

**Input Param：**

n:               输入随机数的个数     
    inputArray:      n个随机整数组成的数组

**Return Value:**

OutputArray    输出处理后的随机整数

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

**输入描述：**

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

**输出描述：**

> 返回多行，处理后的结果

**输入例子：**

11
    10
    20
    40
    32
    67
    40
    20
    89
    300
    400
    15

**输出例子：**

10
    15
    20
    32
    40
    67
    89
    300
    400

### 二、问题分析： ###

按常规思路，首先需要保存输入的值，一个整数和一个整数数组，整数数组可以有多种方式存储，可以用内置类型数组、顺序容器vector或者list或者deque、关联容器set存储。考虑到本题需要完成去重和排序的工作，可以选用关联容器set来存储是最合适的，因为set中没有重复元素，而且set存放的元素默认就是按从小到大排序。

**解题思路1：**

采用set来存储输入数据。

#include <iostream>
    #include <iterator>
    #include <set>
    using namespace std;
    
    int main()
    {
        int num = 0;
        while (cin >> num)
        {
            set<int> st;
            int temp;
            while (num--)
            {
                cin >> temp;
                st.insert(temp);
            }
            for (set<int>::iterator it = st.begin(); it != st.end(); ++it)
            {
                cout << *it << endl;
            }
        }
        return 0;
    }

时间复杂度取决于set的插入操作和遍历操作以及输入的规模。  
空间复杂度为O(n)。

**解题思路2：**  
采用vector来保存输入数据，采用标准库算法unique和sort来实现去重和排序。

#include <iostream>
    #include <vector>
    #include <iterator>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int num, temp;
        while (cin >> num)
        {
            vector<int> vect;
    
            while (num--)
            {
                cin >> temp;
                vect.push_back(temp);
            }
            sort(vect.begin(), vect.end());
            vector<int>::iterator it = unique(vect.begin(), vect.end());
            while (it != vect.end())
            {
                it = vect.erase(it);
            }
            for (vector<int>::iterator it = vect.begin(); it != vect.end(); it++)
            {
                cout << *it << endl;
            }
        }
    }

时间复杂度取决于标准算法库的sort和unique操作以及输入规模。  
空间复杂度为O(n)。

**解题思路3：**

采用内置数组来存储。因为生成的随机数是不超过1000的，所以可以从0遍历到1000，有输入值的置标志位为1，标志位为1的才进行输出。这种解法技巧性较强，也较为浪费存储空间，但是时间效率很高。

#include <iostream>
    using namespace std;
    
    int main()
    {
        int num = 0;
        int a[1001];
        while (cin >> num)
        {
            for (int i = 0; i < 1001; i++)
                a[i] = 0;
            int temp;
            while (num--)
            {
                cin >> temp;
                a[temp] = 1;
            }
            for (int i = 0; i < 1001; i++)
            {
                if (a[i])
                {
                    cout << i << endl;
                }
            }
        }
    
        return 0;
    }

时间复杂度为O(max\{O(n),O(1001)\})  
空间复杂度为O(1001)。

**解题思路4：**

用内置数组存储，不投机取巧，输入所有值，然后排序，去重。这种方式复杂度太高，超出了规定的时间限制。

#include <iostream>
    using namespace std;
    
    void quickSort(int* arr, int a, int b)
    {
        if (a >= b)
            return;
        int i = a + 1, j = b;
        while (i < j)
        {
            while (arr[j] >= arr[a] && j >= i)
                j--;
            while (arr[i] <= arr[a] && i < j)
                i++;
            if (i < j)
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (arr[j] < arr[a])
        {
            int temp = arr[j];
            arr[j] = arr[a];
            arr[a] = temp;
        }
        quickSort(arr, a, j - 1);
        quickSort(arr, j + 1, b);
    }
    
    int main()
    {
        int num = 0;
        int temp;
        while (cin >> num)
        {
            int *a = new int[num];
            for (int i = 0; i < num; i++)
            {
                cin >> temp;
                a[i] = temp;
            }
            if (num >1)
            {
                quickSort(a, 0, num - 1);
                int pre = a[0];
                for (int i = 1; i < num; i++)
                {
                    while (a[i] == pre)
                    {
                        for (int j = i; j < num - 1; j++)
                        {
                            a[j] = a[j + 1];
                        }
                        num--;
                    }
                    pre = a[i];
                }
            }
            for (int i = 0; i < num; i++)
                cout << a[i] << endl;
            delete [] a;
        }
    
        return 0;
    }

时间复杂度为O(n\*n)  
空间复杂度为O(n)。