网站怎么加载图片做logo,阳曲网站建设价格多少,电商公司运营策略,专题网站建设问题描述:
给定一个下标从 0 开始的正整数数组 nums#xff0c;我们的目标是找出并统计满足下述条件的三元组 (i, j, k) 的数目#xff1a;
0 i j k nums.length#xff0c;这确保了三元组索引的顺序性。nums[i]、nums[j] 和 nums[k] 两…问题描述:
给定一个下标从 0 开始的正整数数组 nums我们的目标是找出并统计满足下述条件的三元组 (i, j, k) 的数目
0 i j k nums.length这确保了三元组索引的顺序性。nums[i]、nums[j] 和 nums[k] 两两不同即 nums[i]! nums[j]、nums[i]! nums[k] 且 nums[j]! nums[k]。
暴力解法 - 三层循环遍历
最直观的解法就是使用三层嵌套循环来遍历数组的所有可能组合
#include stdio.h// 函数定义用于找出满足条件的三元组数量
int unequalTriplets(int* nums, int numsSize) {int count 0;for (int i 0; i numsSize - 2; i) {for (int j i 1; j numsSize - 1; j) {for (int k j 1; k numsSize; k) {if (nums[i]! nums[j] nums[i]! nums[k] nums[j]! nums[k]) {count;}}}}return count;
}int main() {int nums[] {1, 2, 3, 4}; // 示例数组你可以替换成其他测试数组int numsSize sizeof(nums) / sizeof(nums[0]);int result unequalTriplets(nums, numsSize);printf(满足条件的三元组数目为: %d\n, result);return 0;
}
在这段代码中
最外层循环控制第一个索引 i它从数组起始位置开始一直到倒数第 3 个位置因为后面还需要留出 j 和 k 的位置。中间层循环控制第二个索引 j它从 i 1 开始确保 j i到倒数第 2 个位置。最内层循环控制第三个索引 k从 j 1 开始保证 k j直到数组末尾。在内层循环里每次都检查当前的三个元素是否两两不等如果是就将计数变量 count 加 1。最终count 存储的就是满足条件的三元组数量。
这种解法简单直接但时间复杂度高达 其中 n 是数组 nums 的长度。在大规模数据面前性能会急剧下降。
优化解法 - 计数与组合数学原理
为了提升效率我们可以换个思路。先统计数组中每个数字出现的频次再利用组合数学的原理来计算满足条件的三元组数量。
#include stdio.h// 函数定义用于找出满足条件的三元组数量
int unequalTriplets(int* nums, int numsSize) {int count 0;// 用于记录每个数字出现的次数int num_count[1001] {0};for (int i 0; i numsSize; i) {num_count[nums[i]];}int left 0;int right numsSize;for (int i 0; i 1001; i) {if (num_count[i] 0) {right - num_count[i];count left * num_count[i] * right;left num_count[i];}}return count;
}int main() {int nums[] {1, 2, 3, 4}; // 示例数组你可以替换成其他测试数组int numsSize sizeof(nums) / sizeof(nums[0]);int result unequalTriplets(nums, numsSize);printf(满足条件的三元组数目为: %d\n, result);return 0;
}
首先创建一个大小为 1001 的数组 num_count假设数组中的数字最大不超过 1000可根据实际情况调整用于记录每个数字在 nums 数组里出现的频次。通过一次遍历 nums 数组将每个数字对应的频次在 num_count 中累加。接着使用两个变量 left 和 right。left 初始化为 0表示当前数字左边不同数字的个数right 初始化为数组长度 numsSize代表当前数字右边不同数字的个数。遍历 num_count 数组时每当遇到一个数字出现次数不为 0 先更新 right将其减去当前数字的出现次数因为这些数字已经被算到当前位置左边或当前位置了不能再算在右边。根据组合数学原理当前数字与左边不同数字和右边不同数字能组成的满足条件三元组数量为 left * num_count[i] * right累加到 count 中。最后更新 left将当前数字的出现次数累加到 left 上准备处理下一个数字。
这种优化后的解法时间复杂度降低到 其中 n 是数组 nums 的长度m 是数组中不同数字的个数。相比暴力解法大大提高了计算效率。
总结与拓展:
从简单直接但低效的暴力解法到巧妙利用数据统计和数学原理的高效解法效率得到了质的飞跃。在实际编程中面对类似问题我们应多思考数据的内在规律尝试从不同角度去拆解问题运用合适的数学知识或数据结构来优化算法。
希望通过这篇博客大家对数组计数类算法问题有了更清晰的理解也能在日后的编程实践中灵活运用这些思路去攻克难题。
