码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift
  • 【力扣每日一题】2023.10.19 同积元组


    目录

    题目:

    示例:

    分析:

    代码:


    题目:

    示例:

    分析:

    题目比较简洁,给我们一个元素各不相同的数组,要我们找出该数组里能够组成 a*b=c*d 的组合数目。

    比较直观的做法是我们直接暴力枚举,不过这肯定是会超时的,所以我们需要优化一下。

    我们把题目换个说法,a*b=c*d 那就是两组乘积相同的数,所以我们就改为一共有多少两组乘积相同的数,得出来的结果需要乘8,因为abcd是可以调换顺序的,就算是同样的4个数,也会产生出8种不同的排列组合。

    接下来我们就只需要找出数组中有多少两两相乘的乘积相同的数。

    题目给的示例中的解释把答案的元组全列出来了,有些许的误导,实际上我们并不需要知道符合答案的元组是什么,我们只要求出元组数量即可。

    所以我们两层for循环把数组中任意两个数都给乘一边,把每两个数之前的乘积的所有可能都获取到,用一个map来接收,键是乘积,值是乘积出现的次数。

    获取完毕之后我们就得到了所有可能出现的乘积以及能够凑成乘积的元素组数。任意两个组都可以凑成一个a*b=c*d,并且根据我们之前的分析,每凑成一个我们都能得到8种答案。

    我们初中应该都学过排列组合,假设能凑成乘积为i的一共有n个组,那么这n个组两两配对,一共会有这么多种可能。

    因此把map遍历一边,套这个公式就等得出有多少两组数乘积相同的数量了,最后把这个结果再乘8即可。

    代码:

    1. class Solution {
    2. public:
    3. int tupleSameProduct(vector<int>& nums) {
    4. unordered_map<int,int>m;
    5. for(int i=0;isize();++i){
    6. for(int j=i+1;jsize();++j){
    7. //获取任意两个元素的乘积数
    8. m[nums[i]*nums[j]]++;
    9. }
    10. }
    11. int res=0;
    12. for(auto& p:m){
    13. //从n里面选出2的排列组合总数
    14. res+=(p.second*(p.second-1)/2);
    15. }
    16. return res*8;
    17. }
    18. };

  • 相关阅读:
    Java大总结之——静态方法和静态变量+代码块+抽象类+接口+单例设计模式+模版设计模式
    .NET 发布,部署和运行应用程序
    PostGIS是否有方法能将一个Polygon面切割成若干份小的Polygon面,且每一份的面积差不多大
    5-1继承的练习
    用winsw将nodejs项目的exe程序安装为服务
    汽车以太网协议栈
    Linux 简要命令记录
    Android 7.1 音量定制限定在0-80%之间可调节
    第1章Linux基础篇-Linux入门
    redolog、undolog和binlog日志文件详解
  • 原文地址:https://blog.csdn.net/m0_63235356/article/details/133918301
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常,环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧!!!
    奉劝各位学弟学妹们,该打造你的技术影响力了!
    五年了,我在 CSDN 的两个一百万。
    Java俄罗斯方块,老程序员花了一个周末,连接中学年代!
    面试官都震惊,你这网络基础可以啊!
    你真的会用百度吗?我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候,用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难,连憨憨学妹都学会了!
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图,Python爬虫120例,再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号