算法零基础——计数数组

目录

引言(计数法与计数数组)

唯一元素的和

找到所有数组中消失的数字

好数对的数目

检查是否所有字符出现次数相同

字符串中的第一个唯一字符


引言(计数法与计数数组)

我们经常用一个奇数元素来统计元素出现的次数

如我们统计智商超过163的有多少人,就可以用一个计数法

1
2
3
4
5
6
7
8
9
int func(int *iq, int size) {
int cnt = 0;
for(i = 0; i < size; ++i) {
if(iq[i] > 163) {
++cnt;
}
}
return cnt;
}

假如我们想知道iq的分布呢,那么我们就可以使用一个计数数组,我们可以把iq的值映射到计数数组的下标,其所对应的值就是这个元素出现的次数

1
2
3
4
5
6
7
8
9
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)
}

唯一元素的和

唯一元素的和

给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。

请你返回 nums 中唯一元素的  。

示例 1:

输入:nums = [1,2,3,2]
输出:4
解释:唯一元素为 [1,3] ,和为 4 。

示例 2:

输入:nums = [1,1,1,1,1]
输出:0
解释:没有唯一元素,和为 0 。

示例 3 :

输入:nums = [1,2,3,4,5]
输出:15
解释:唯一元素为 [1,2,3,4,5] ,和为 15 。

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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;
}

找到所有数组中消失的数字

找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。

示例 1:

输入:nums = [4,3,2,7,8,2,3,1]
输出:[5,6]

示例 2:

输入:nums = [1,1]
输出:[2]

提示:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

有n个元素的数组原本里面的元素应该是1到n ,我们需要找到这其中没出现的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* 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;//返回那个元素的数组
}

好数对的数目

好数对的数目

给你一个整数数组 nums

如果一组数字 (i,j) 满足 nums[i] == nums[j]i < j ,就可以认为这是一组 好数对

返回好数对的数目。

示例 1:

输入:nums = [1,2,3,1,1,3]
输出:4
解释:有 4 组好数对,分别是 (0,3), (0,4), (3,4), (2,5) ,下标从 0 开始

示例 2:

输入:nums = [1,1,1,1]
输出:6
解释:数组中的每组数字都是好数对

示例 3:

输入:nums = [1,2,3]
输出:0

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

假如一个元素出现3次,他的对数是3,加个元素出现4次,他的对数是6 ,那么我们就可以用一个计数数组来接收,假如他计数数组的值大于1,那么他的对数就是Cn2,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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;



}

检查是否所有字符出现次数相同

检查是否所有字符出现次数相同

给你一个字符串 s ,如果 s 是一个  字符串,请你返回 true ,否则请返回 false 。

如果 s 中出现过的 所有 字符的出现次数 相同 ,那么我们称字符串 s 是  字符串。

示例 1:

输入:s = “abacbc”
输出:true
解释:s 中出现过的字符为 ‘a’,’b’ 和 ‘c’ 。s 中所有字符均出现 2 次。

示例 2:

输入:s = “aaabb”
输出:false
解释:s 中出现过的字符为 ‘a’ 和 ‘b’ 。
‘a’ 出现了 3 次,’b’ 出现了 2 次,两者出现次数不同。

提示:

  • 1 <= s.length <= 1000
  • s 只包含小写英文字母。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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;
}

字符串中的第一个唯一字符

字符串中的第一个唯一字符

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

示例:

s = “leetcode”
返回 0

s = “loveleetcode”
返回 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
}

算法零基础——计数数组
http://example.com/2021/11/26/算法零基础——计数数组/
作者
Zevin
发布于
2021年11月26日
许可协议