当前位置: 首页 > news >正文

国外数据网站广东免费网络推广软件

国外数据网站,广东免费网络推广软件,济南专业的设计网站,最近的新闻热点时事问题描述: 给定一个下标从 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) 的数目:

  1. 0 <= i < j < k < nums.length,这确保了三元组索引的顺序性。
  2. 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 存储的就是满足条件的三元组数量。

这种解法简单直接,但时间复杂度高达 o(n^{3}),其中 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 和 rightleft 初始化为 0,表示当前数字左边不同数字的个数;right 初始化为数组长度 numsSize,代表当前数字右边不同数字的个数。
  • 遍历 num_count 数组时,每当遇到一个数字出现次数不为 0:
    • 先更新 right,将其减去当前数字的出现次数,因为这些数字已经被算到当前位置左边或当前位置了,不能再算在右边。
    • 根据组合数学原理,当前数字与左边不同数字和右边不同数字能组成的满足条件三元组数量为 left * num_count[i] * right,累加到 count 中。
    • 最后更新 left,将当前数字的出现次数累加到 left 上,准备处理下一个数字。

这种优化后的解法时间复杂度降低到 ,其中 n 是数组 nums 的长度,m 是数组中不同数字的个数。相比暴力解法,大大提高了计算效率。

总结与拓展:

从简单直接但低效的暴力解法,到巧妙利用数据统计和数学原理的高效解法,效率得到了质的飞跃。在实际编程中,面对类似问题,我们应多思考数据的内在规律,尝试从不同角度去拆解问题,运用合适的数学知识或数据结构来优化算法。

希望通过这篇博客,大家对数组计数类算法问题有了更清晰的理解,也能在日后的编程实践中灵活运用这些思路去攻克难题。

 

http://www.tj-hxxt.cn/news/1698.html

相关文章:

  • 做网站的公司是什么seo排名赚app
  • 网站建设文化传播有限公司免费的网页制作软件
  • 香港赛马会网站怎么做国际域名注册网站
  • 无网站如何做淘宝客2345网址导航设为主页
  • 响应式企业网站设计与实现申请自媒体平台注册
  • 二手车为什么做网站长沙网络推广营销
  • lnmp搭建网站杭州小程序建设公司
  • 大型网站建设费用平台推广是什么
  • 北京商场关门网站优化推广平台
  • 提交网站亚马逊关键词排名查询工具
  • 微信上的网站怎么做的吗发帖推广平台
  • 网站开发用的工具苏州网络推广seo服务
  • 做网站用的产品展示横幅怎样做推广是免费的
  • 电子商务网站建设课件网站接广告
  • wordpress导航背景图片深圳seo网站推广方案
  • 绵阳辉煌网站建设今日国内新闻最新消息大事
  • 怎么下学做衣服网站北京搜索优化推广公司
  • 德州市平原县建设局网站河南网站排名
  • 莱芜网站优化登录百度账号
  • wordpress增加导航栏seo关键词优化软件
  • 在线做txt下载网站友链交易平台
  • 秦皇岛营销式网站制作电商运营
  • 做网站靠教育赚钱日照高端网站建设
  • 网站建设书籍138ip查询网域名解析
  • 上海app设计公司seo搜索引擎优化人才
  • 自己做网站需要多少资金网站优化方法
  • 海口新闻网seo能从搜索引擎中获得更多的
  • 上海高端网站设计网络推广计划制定步骤
  • 中山电商网站制作百度竞价品牌广告
  • 注册了域名之后怎么做网站天津抖音seo