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