本文共 1576 字,大约阅读时间需要 5 分钟。
本题的目的是统计数组中x+1的个数,假设 arr = {1,1,2,3,3},那么 x+1 分别是 {2,2,3,4,4} ,其中 2 和 3 都在 arr 中,因此个数为 3。
需要注意的一点就是 arr 可能存在重复数字,对于 arr = {1,1,1,2} 来说,最大值 2 的 x+1 肯定不在 arr 中,而 arr 三个重复的 1 的 x+1 是 2,因此个数为 3。
需要定义一个数组 hash[] ,索引对应 arr 中的元素值,值为在 arr 中的重复次数。例如对于 arr = {1,1,1,2} 来说,hash[1] = 3,因为元素 1 重复了 3 次。
有了 hash[] 数组后,只需要判断 hash[x+1] 是否不为 0 即可,因为如果 hash[x+1] = 0,说明 x+1 在 arr 中的重复次数为 0,换句话说 x+1 不存在与 arr 中。因此遍历 hash[] 数组,统计不为 0 的个数即可。
在实际操作中,不可能用绝对位置,这样会浪费很多空间,而是用相对位置,先找出 arr 最小值和最大值,然后 hash[] 的容量为 max - min + 1。例如 arr = {3,4,3,7,8},那么 hash[] 的容量为 8 - 3 + 1 = 6,因此 hash[1] 表示的是 min+1 在 arr 中的重复次数,即 hash[1] 表示的是元素 3 在 arr 中的重复次数。
确定 hash[] 数组后,就开始遍历 hash[] 数组,统计不为 0 的个数即可。但是注意我们找的是 x+1 ,因此对 hash[] 的遍历范围是第 1 个到最后一个(索引从第 0 个开始)。
int countElements(int* arr, int arrSize){ int cnt = 0; int max = INT_MIN; // 存储 arr 中的最大值 int min = INT_MAX; // 存储 arr 中的最小值 // 下面 for 循环是找出最大值和最小值 for (int i = 0; i < arrSize; i++) { max = max > arr[i] ? max : arr[i]; min = min < arr[i] ? min : arr[i]; } int hashSize = max - min + 1; // 确定 hash[] 数组的容量 int *hash = (int *)calloc(hashSize, sizeof(int)); // 申请内存创建 hash[] 数组 // hash[] 数组赋值 for (int i = 0; i < arrSize; i++) { hash[arr[i] - min]++; // arr[i] - min 表示相对位置,以 0 作为 min 在 hash[] 中的索引 } for (int i = 0; i < arrSize; i++) { // arr[i] + 1 - min < hashSize 作用是防止访问越界,因为 max + 1 肯定不在 arr 中 // arr[i] + 1 即 x + 1 if (arr[i] + 1 - min < hashSize && hash[(arr[i] + 1) - min]) { cnt++; } } return cnt;}
转载地址:http://kbtin.baihongyu.com/