首页 > 其他分享 >1726. 同积元组

1726. 同积元组

时间:2023-10-20 11:24:05浏览次数:34  
标签:cnt nums 1726 同积 times int 哈希 ans 元组

1.题目介绍

2.题解

2.1 方法一:哈希统计

思路与算法

假设当前给定元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 满足 a×b=c×d,且此时满足 a≠b≠c≠d,则可以知道该元组可以按照不同顺序组合,组成 8 个不同的元组,
且这个8个元组均满足题目要求:
(a,b,c,d),(a,b,d,c)
(b,a,c,d),(b,a,c,d)
(c,d,a,b),(c,d,b,a)
(d,c,a,b),(d,c,b,a)

也就是说,我们只需要统计出乘积 i1*i2 = n(定值) 的二元组(i1,i2)数量,存入\(cnt(a\times b)\)中,然后从中不断选出两个二元组自由组合,\(C_{cnt(a\times b)}^2 \times 8\) 也就是最后的结果。换算成表达式也就是\(\frac{cnt(a\times b)\times(cnt(a\times b)-1)}2\times8\)
所以说现在的问题就是如何统计\(cnt(a\times b)\)
这里很显然的是个统计出现次数的问题,我们理所当然的想到了哈希表统计
只要组织键值对pair(\(a\times b\), 出现次数)即可

代码

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++)
            for (int j = i + 1; j < nums.size(); j++){
                map[nums[i]*nums[j]]++;
            }
        int ans = 0;
        for (auto &pair : map){
            ans += (pair.second) * (pair.second - 1) * 4;
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度:\(o(n^2)\),双重循环
  • 空间复杂度:\(o(n^2)\),最坏情况下一共有O(n²)种乘积,例如nums全是质数的情况下

2.2 优化?

在官方题解中,我们先用哈希表统计各乘积的出现次数,在最后遍历哈希表计算总个数。这里我们换个思路呢,能否在统计出现次数的时候同时计算总个数呢?这样就可以优化遍历哈希表的循环时间。
答案是肯定可以的,在每次使用一个二元组\(( nums[i] ,nums[j])\)计算出一个乘积后,我们便可以直接从哈希表中寻找与其匹配的二元组个数,这里面的每个二元组都能与其构成8个组合,且并不会与之前的组合产生任何重复(固定有一组新的二元组\(( nums[i] ,nums[j])\),直接进行总个数的计算即可 \(ans += 8 * productCount[product];\).
这里若是从计算公式来比较,答案中的\(\frac{cnt(a\times b)\times(cnt(a\times b)-1)}2\times8:\)形式是不是感觉很熟悉?没错,就是等差数列求和公式,\(ans += 8 * productCount[product];\)的计算方式实际上就是将其拆分成了\(8\times (1+2+...+[cnt(a\times b) - 1 ]) = 8 \times \frac{[1 + cnt(a\times b) - 1]\times(cnt(a\times b)-1)}2 = \frac{cnt(a\times b)\times(cnt(a\times b)-1)}2\)

class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> productCount;

        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int product = nums[i] * nums[j];
                ans += 8 * productCount[product];
                productCount[product]++;
            }
        }
        return ans;
    }
};

标签:cnt,nums,1726,同积,times,int,哈希,ans,元组
From: https://www.cnblogs.com/trmbh12/p/17776617.html

相关文章

  • 力扣-2367-算术三元组的数目
    给你一个下标从0开始、严格递增的整数数组nums和一个正整数diff。如果满足下述全部条件,则三元组(i,j,k)就是一个算术三元组:i<j<k,nums[j]-nums[i]==diff且nums[k]-nums[j]==diff返回不同算术三元组的数目。 示例1:输入:nums=[0,1,4,6,7,10],di......
  • C#教程 - 元组与解构(Tuples and Deconstruction )
    C#教程-元组与解构(TuplesandDeconstruction) 更新记录转载请注明出处:2022年9月24日发布。2022年9月10日从笔记迁移到博客。元组(tuples)说明#注意:C#7.0可用注意:元组不可以声明为静态类型作用:元组常用于传递和返回多个值;匿名类型可以做的,Tuples基本都可以完成元组是......
  • Essential .NET - C# 7.0:细说元组
    Essential.NET-C#7.0:细说元组作者 MarkMichaelis在去年11月的Connect();专题(msdn.microsoft.com/magazine/mt790178)中,我概述了C#7.0,并介绍了元组。在本文中,我将重新深入探究元组,并全方位地介绍语法选项。首先,让我们来想想下面这个问题:为什么要使用元组?有时,可......
  • C# 元组的demo
      //Seehttps://aka.ms/new-console-templateformoreinformationConsole.WriteLine("Hello,World!");stringname="马良";intage=16;vara=(Name:name,Age:age,1,2,3,4,5,6,7,8,9,0);(stringa1,inta2)=(name,age);varun......
  • Python入门示例系列14 元组
    Python入门示例系列14元组 Python的元组与列表类似,不同之处在于元组的元素不能修改。元组使用小括号(),列表使用方括号[]。元组创建只需要在括号中添加元素,并使用逗号隔开即可。示例:>>>t4=(1,2,3,4)#四个整数的元组>>>t4(1,2,3,4)>>>t1=()#空元祖>>>t1()>>......
  • TypeScript入门到精通——TypeScript类型系统基础——元组类型
    TypeScript类型系统基础——元组类型 元组(Tuple)表示由有限元素构成的有序列表。在JavaScript中,没有提供原生的元组数据类型。TypeScript对此进行了补充,提供了元组数据类型。由于元组数组之间存在很多共性,因此TypeScript使用数组来表示元组。 在TypeScript中,元组类型......
  • 深挖 Python 元组 pt.1
    哈喽大家好,我是咸鱼好久不见甚是想念,2023年最后一次法定节假日已经结束了,不知道各位小伙伴是不是跟咸鱼一样今天就开始“搬砖”了呢?我们知道元组(tuple)是Python的内置数据类型,tuple是一个不可变的值序列tuple的元素可以是任何类型,一般用在存储异构数据(例如数据库记录)的场景......
  • Python 元组完全指南2
    更新元组更改元组的值元组是不可更改的,但有一种变通方法。您可以将元组转换为列表,更改列表,然后将列表转换回元组。示例:x=("apple","banana","cherry")y=list(x)y[1]="kiwi"x=tuple(y)print(x)添加项由于元组是不可变的,没有内置的append()方法,但可以使用其他......
  • Python 元组完全指南1
    元组用于在单个变量中存储多个项目。mytuple=("apple","banana","cherry")元组是Python中的4种内置数据类型之一,用于存储数据集合,另外还有列表、集合和字典,它们都具有不同的特性和用途。元组是有序且不可更改的集合。元组使用圆括号表示。示例,创建一个元组:thistuple=......
  • 算法题:牛牛的三元组问题
    牛牛的三元组问题_牛客题霸_牛客网描述动物牛牛是一个勇敢的冒险家,它正在探索一个神秘的岛屿。岛上有许多宝藏,但是宝藏被隐藏在一系列数字中。牛牛找到了一个整数数组 nums,它相信这个数组中存在一些特殊的三元组,满足以下条件:三元组的和等于0。三元组中的元素不能重复。牛牛想按照......