[数据结构与算法]简单哈希表，计数哈希，c++

哈希常用来提速，以空间换时间，看到时间很快，内存很大不要诧异

#include <stdio.h>//这是c语言
#include <string.h>
#define maxn 1000001
int hash[maxn];//定义一个较大的数组
int main() {
    int n, x;
    int i, j;
    int hasPrint;//hasprint有个很重要的作用就是判断这个数是否已经出现过了
    while(scanf("%d", &n) != EOF) {   
        memset(hash, 0, sizeof(hash)); //将哈希数组中的所有元素都赋值为0        
        while(n--) {
            scanf("%d", &x);//输入n组数据，即n个x
            ++hash[x];  //将下标为x的位置加1                    
        }
        hasPrint = 0;//刚开始置为0
        for(i = 0; i < maxn; ++i) {//遍历所有数      
            if(hash[i]) {//如果不为0
                for(j = 0; j < hash[i]; ++j) {//hash[i]里面存的数就是x的个数
                    if(hasPrint) {//如果已经输出过数就输出一个空格
                         printf(" ");   
                    }
                    printf("%d", i);//输出这个i，即为x
                    hasPrint = 1;//证明已经输出过数字了
                }
            }
        }
        printf("\n");//换行准备输入下一组数据
    }
    return 0;
}//这就是一个不用排序用哈希把一组无序的数字排列有序

其实这种排序不算是排序，而是将输入的x变为数组下标，然后记录x的数量，因为前面已将数组清0，所以只需要遍历所有数寻找不为0的那个数组下标，对应的输出i值，就相当于排序了

下面有几道力扣的类似题

448. 找到所有数组中消失的数字 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/在介绍代码之前我要介绍一下auto &num:nums，这个在for循环中就代表了遍历nums数组，称不上数组，其实是array和vector容器，是c++中特有的遍历方式，&是一个引用符号，只需要记住

遍历nums中的每一个数，num就是数组中的数字，下面的代码将能更加详细的理解这

理解之后我们看题

?

//这是c++做法
class Solution {//核心思想将nums看做哈希
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
int n=nums.size();
for(auto &num:nums)
{
    nums[(num-1)%n]+=n;//主要思想就是遍历数组，找出小于n的数，则证明这个数未出现过，其中有一种特判就是[1,1]这就是用num-1的愿意
}
vector<int>ret;
int l=0;
for(int i=0;i<n;i++)
{
    if(nums[i]<=n)
    {
        ret.push_back(i+1);//vector库函数
    }
}
return ret;
    }
};

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){
int *hash=(int *)malloc(sizeof(int)*(numsSize+1));//c语言哈希较慢
int *ret=(int *)malloc(sizeof(int)*(numsSize+1));
memset(hash,0,sizeof(int)*(numsSize+1));
for(int i=0;i<numsSize;i++)
{
    ++hash[nums[i]];//计数，思想就是出现的数都会递增，而未出现的数则为0
}
int l=0;//用于给数组中存数
for(int j=1;j<=numsSize;j++)
{
    if(!hash[j])//如果等于0则证明没有出现过
    {
        ret[l++]=j;
    }
}
*returnSize=l;//必须告知数组的长度
return ret;
}