LeetCode 2475 数组中不等三元组的数目

ops/2024/12/19 16:18:19/

问题描述:             

给定一个下标从 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.ppmy.cn/ops/143222.html

相关文章

Github 2024-12-15 php开源项目日报Top10

根据Github Trendings的统计,今日(2024-12-15统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量PHP项目10Matomo:开源网站分析平台 创建周期:4687 天开发语言:PHP协议类型:GNU General Public License v3.0Star数量:18681 个Fork数量:…

linux 替换yum源镜像

1. 备份源镜像 sudo cp /etc/yum.repos.d/CentOS-Base.repo /etc/yum.repos.d/CentOS-Base.repo.bak 2. 下载国内镜像阿里云 如果没有wget可以用curl 代替 sudo wget -O /etc/yum.repos.d/CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-7.repo 清华大学 sudo wget -…

【云原生】Docker Compose 从入门到实战使用详解

目录 一、前言 二、Docker Compose 介绍 2.1 Docker Compose概述 2.2 Docker Compose特点 2.3 Docker Compose使用场景 三、Docker Compose 安装 3.1 安装docker环境 3.2 Docker Compose安装方式一 3.2.1 下载最新版 3.2.2 设置权限 3.2.3 设置软链接 3.2.4 查看版本…

局部规划器设计思路

本文参考知乎文章:如何设计局部规划器 0 引言 局部规划器设计通用方法:生成路径——>寻找最优路径——>后处理优化 1 路径生成 四个问题: ① 如果全局路径中突然出现动态障碍物 ② 如果全局路径非常靠近障碍物 ③ 如果全局路径不容易跟踪(B样条平滑) ④ 如果全局…

React 工具和库面试题(一)

1. 如何在 React 项目中使用 Hooks 从服务端获取数据&#xff1f; 在 React 中&#xff0c;我们通常使用 useEffect Hook 来进行副作用操作&#xff0c;比如从服务端获取数据&#xff0c;结合 useState 来管理数据状态。 基本步骤&#xff1a; 使用 useEffect 来执行异步操作…

一般p维正态随机向量的二次型

内容来源 应用多元统计分析 北京大学出版社 高惠璇编著 1 设 X ∼ N p ( μ , Σ ) , Σ > 0 X\sim N_p(\mu,\Sigma),\Sigma>0 X∼Np​(μ,Σ),Σ>0 则 X ′ Σ − 1 X ∼ χ 2 ( p , δ ) X\Sigma^{-1}X\sim\chi^2(p,\delta) X′Σ−1X∼χ2(p,δ)&#xff0c;其…

【AutoDL】通过【SSH远程连接】【vscode】

小帅碎碎念 0. 起因1. SSH信息获取2. 给你的vscode安装支持SSH远程连接的插件3. SSH远程连接入口4. 输入密码登陆5. 总结 0. 起因 之前使用AutoDL和Jupyter进行代码编辑和执行确实很方便&#xff0c;尤其是对于交互式数据分析项目。然而&#xff0c;也存在一些限制和不便之处&…

RabbitMQ安装延迟消息插件(mq报错)

之前启动一个springboot的单体项目&#xff0c;一直mq的错误&#xff0c;即便我更新了最新版本的mq&#xff0c;还是报错。 后来才发现&#xff0c;项目使用了延时队列&#xff0c;是需要单独下载延时插件的。 1如果判断mq有没有延时队列插件【没有x-delayed-message】 2下载…