目录
引言（计数法与计数数组）
我们经常用一个奇数元素来统计元素出现的次数
如我们统计智商超过163的有多少人，就可以用一个计数法
int func(int *iq, int size) { int cnt = 0; for(i = 0; i < size; ++i) { if(iq[i] > 163) { ++cnt; } } return cnt; }
假如我们想知道iq的分布呢，那么我们就可以使用一个计数数组，我们可以把iq的值映射到计数数组的下标，其所对应的值就是这个元素出现的次数
int *func(int *iq, int size, int IQMax) { // (1）*iq就是他数组元素，size就是这个元素的长度，iqmax就是智商的上限 int i; int *cnt = (int *)malloc( sizeof(int) * (IQMax+1) ); // (2)弄一个计数的数组，其最大值为iqmax+1，因为他要映射到数组的下标 memset(cnt, 0, sizeof(int) * (IQMax+1)); // (3)对他进行初始化赋值为0，后续进行操作 for(i = 0; i < size; ++i) { ++cnt[ iq[i] ]; // (4)//把iq的值赋给cnt的下标，后期对cnt进行遍历就可以了 } return cnt; // (5) }
唯一元素的和
int sumOfUnique(int* nums, int numsSize) { int cnt[101];//由于nums[i]的上限就是100，所以把他计数数组的下标定义的最大值为101， memset(cnt,0,sizeof(cnt));//把他赋为0 int i=0; int sum=0; for(i=0;i<numsSize;i++) { ++cnt[nums[i]];//对计数数组进行统计 } for(i=0;i<101;i++) { if(cnt[i]==1)//假如只出现一次，就把他的下标加起来 { sum+=i; } } return sum; }
找到所有数组中消失的数字
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) { int cnt[numsSize+1];//定义计数数组，最大元素应当映射到n，所以就+1 memset(cnt,0,sizeof(cnt));//对他初始化为0，之后对计数数组填充后，找到那个出现次数为0的即可 int i=0; for(i=0;i<numsSize;i++) { cnt[nums[i]]++; } int j=0; for(i=1;i<numsSize+1;i++)//因为i=0，0也只出现0次，但 题目要求我们是从1开始，所以i从1开始 { if(cnt[i]==0) { j++;//因为我们要malloc出来一个数组来接收那些只出现一次的元素，所以要计算那个数组里面有多少个元素 } } int *ret=(int *)malloc(sizeof(int)*j); int k=0; for(i=1;i<numsSize+1;i++) { if(cnt[i]==0) { ret[k++]=i;//把只出现过一次的赋给ret } } *returnSize=j; return ret;//返回那个元素的数组 }
int consist(int n,int m)//计数这个大于1的数的对数 { int sum1=1; int sum2=1; int sum; int i=n; int j=1; for(j=1;j<=m;j++) { sum1*=j; } while(m--) { sum2*=i; i--; } sum=sum2/sum1; return sum; } int numIdenticalPairs(int* nums, int numsSize) { int n=numsSize; int cnt[101]; memset(cnt,0,sizeof(cnt)); int i=0; for(i=0;i<n;i++) { ++cnt[nums[i]]; } int flag=1; int sum=0; for(i=1;i<101;i++) { if(cnt[i]!=0&&cnt[i]!=1) { sum+=consist(cnt[i],2); } } return sum; }
检查是否所有字符出现次数相同
bool areOccurrencesEqual(char * s) { int cnt[26];//因为里面每个元素都是小写字母 memset(cnt,0,sizeof(cnt)); int len=strlen(s); int i=0; for(i=0;i<len;i++) { ++cnt[s[i]-'a'];//-‘a’，假如‘a’-‘a’=0；，字母也就映射到了下标 } int flag=1; for(i=0;i<len-1;i++) { if(cnt[s[i]-'a']!=cnt[s[i+1]-'a'])//出现的次数用s[i]来因数，假如前后对应出现的次数不相同就是错的，前后总能把所有元素进行比对完 { return false; } } return true; }
字符串中的第一个唯一字符
int firstUniqChar(char * s) { int len=strlen(s); int cnt[26]; memset(cnt,0,sizeof(cnt)); int i=0; for(i=0;i<len;i++) { ++cnt[s[i]-'a']; } for(i=0;i<len;i++) { if(cnt[s[i]-'a']==1) { return i;//遇到第一个只出现一次的就返回 } } return -1;//循环的都没找到就返回-1 }
