算法零基础——计数数组

目录

引言（计数法与计数数组）

唯一元素的和

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

好数对的数目

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

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

引言（计数法与计数数组）

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

如我们统计智商超过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日
许可协议