题解 | #计算某字母出现次数#

明明的随机数

http://www.nowcoder.com/practice/3245215fffb84b7b81285493eae92ff0

题目分析

输入的第一个数字N表示接下来一组要继续输入N个数字，这N+1个数字作为一组

题目要求N个数字要进行去重并重新排序输出

题目会给出若干组数字，对每一组数组都要像前面的处理，追加在上一轮的输出后面即可

方法一：普通sort排序

实现思路
- 对于每一组的数字首先装进nums向量中，不去重
- 直接对nums调用sort函数直接排序
- 排序后作为一个有序递增数组，可以用双指针的方法进行去重，只输出不重复的部分
- 最后对于每一组都这样处理即可

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int n;
    while(cin >> n) {                        // 输入个数N
        vector<int> nums;                    // 储存每一轮的所有生成的N个数字
        while(n) {                           // 处理输入和写入N个数字
            int a;
            cin >> a;
            nums.push_back(a);
            n--;
        }
        sort(nums.begin(), nums.end());      // 对该轮的数字进行排序，其中可能包含重复的数字
        
        for(int i = 0; i < nums.size();) {   // i指针标记一个位置
            int j = i + 1;                   // j指针开始从i指针后一个位置往后找
            for(; j < nums.size() && nums[i] == nums[j]; j++);    // 直到j指针找到下一个与i指针指向的数字不同的位置
            cout << nums[i] << endl;         // 输出所有i指针所指的数字，一定都是不重复的
            i = j;
        }
    }
    return 0;
}

复杂度分析

时间复杂度： $O (n l o g n)$ ，其中开销最大的部分就是排序sort函数部分，代价为 $O (n l o g n)$
空间复杂度： $O (n)$ ，需要借助辅助nums数组装载所有的数字

方法二：桶排序

实现思路
- 由于题目规定随机生成的数字范围在[1,1000]中，对于这种类型有限的排序可以考虑桶排序的方案
- 我们只要准备一个1001长度的容器，进行对每一个数字出现标记工作即可
- 然后按照索引顺序和标记顺序可以实现排序工作
- 并且标记也可以帮我们实现去重工作
- 最后输出排序结果即可

alt

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n;

    while(cin >> n) {                        // 输入个数N
        int a[501] = {0};                   // 直接用一个1001大小的数组存储出现的数字
        while(n) {                           // 对N个数字进行处理
            int num;
            cin >> num;                      // 分别输入这一轮的N个数字
            a[num] = 1;                      // 对出现的数字标记为1
            n--;
        }
        for(int i = 0; i < 501; i++) {
            if(a[i] == 1) cout << i <<endl;  // 每一轮根据桶排序的原理进行按序输出
        }
    }
    return 0;
}