题目描述

输入

输出

示例输入

3
1 1 2

示例输出

1 2

首先声明本渣还没学会哈希，这篇就当哈希的预习篇吧 写的不好大家见谅

首先说一下我最初的思路，因为要统计出现次数，所以第一反应是对于每一个数字对应一个键值，我们建这么一个数组 h[10000000] 比如对于输入这么一串数字1 2 2 4 9 其中1对应h[1] 2对应h[2] 4对应h[4] 总结一下就是i 对应 h[i]， 每扫到一个数字i ,h[i]++，那么最终就会统计完所有数字出现的数字  but,当我提交了之后意料之中的没有过，怎么回事？超内存了，是的我们可以看到每一个数字的范围是在一亿以内，就意味着我们需要声明一个一亿大小的h[],但实际上只有10000个数字，会有大量的空间用不到，怎么办呢？书上说可以对一个大的素数取余，但那样的话就会产生冲突了，不难想象吧，比如还是上面那串数字，假设h[]大小为5（对5取余）,那么数字4 和数字9都会对应同一个键值 h[4]

怎么办？书上说要将hash表的每一个位置做成一个链表（原谅我 我没看懂，暑假我要好好学数据结构！）难道就不能做了吗，网上看到某大牛的解法（大牛好像都不爱写解题报告，意识流选手orz），看了半天终于算是看出点道道来了 在说之前，先讲两个函数（STL模板里面的）我也是现学的，一个是upper_bound(a,a+n,a[i]) 他返回容器里面第一个大于a[i]的元素的下标，另一个是lower_bound(a,a+n,a[i]) 返回容器里面第一个大于等于a[i]的元素的下标 还是看上面的那串数字（已sort） 1 2 2 4 9 upper 返回值依次是1 3 3 4 5（注意最后一个，数组会越界） lower的返回值依次是0 1 1 3 4 然后另upper-lower 得到 1 2 2 1 1 仔细观察 他们是不是正是对应位置数字出现的次数？这算不算也是一种哈希？这样 有多少个数字我们就可以只声明多大的数组就可以了。