Ссылка на задачу – 1726. Tuple with Same Product.
📜 Описание задачи
Дан массив nums из различных положительных чисел. Нужно вернуть количество кортежей (a, b, c, d), таких что произведение a * b равно произведению c * d, при условии, что все элементы кортежа различны.
💡 Идея
- Для каждой уникальной пары элементов из массива nums вычисляем произведение и подсчитываем частоту его появления с помощью HashMap.
- Для каждого произведения, встречающегося больше одного раза необходимо учесть, что существует 8 уникальных вариантов составления кортежей:
a*b=c*d; a*b=d*c; b*a=c*d; b*a=d*c; c*d=a*b; c*d=b*a; d*c=a*b; d*c=b*a
- Соответственно, итоговый вклад, каждого произведения вычисляется как
4 * frequency * (frequency - 1)
🔍 Детали подхода
- Подсчет в HashMap:
- Используем два вложенных цикла для перебора всех уникальных пар
(i, j) с условием i < j и вычисляем их произведение.
- Результаты произведений сохраняем в
HashMap, где ключ — это само произведение, а значение — количество его вхождений.
- Расчет кортежей:
- Для каждого произведения с частотой больше
1, добавляем в итоговый результат значение
4 * frequency * (frequency - 1).
- Возврат результата:
- Итоговый результат суммируется и возвращается.
⏱️ Асимптотика
- Временная сложность
O(n²):
- Два вложенных цикла перебирают все пары элементов массива размером n.
- Пространственная сложность
O(n²):
- В худшем случае все произведения будут уникальными, и HashMap будет хранить порядка n*(n-1)/2 элементов.
💻 Исходный код
use std::collections::HashMap;
impl Solution {
pub fn tuple_same_product(nums: Vec<i32>) -> i32 {
let n = nums.len();
// Map to store the count of each product computed from unique pairs.
let mut product_count: HashMap<i32, i32> = HashMap::new();
// Iterate over all unique pairs (i, j) with i < j.
for i in 0..n {
for j in i + 1..n {
let product = nums[i] * nums[j];
// Increment the count for the computed product.
*product_count.entry(product).or_insert(0) += 1;
}
}
// Sum the contributions for each product (only counts > 1 contribute).
// Each product contributes count * (count - 1)/2 tuple pairs, then multiplied by 8.
4 * product_count.values().map(|cnt| cnt * (cnt - 1)).sum::<i32>()
}
}
Tags: #rust #algorithms #frequencies
На практических масштабах решение со сложностью O(N²logN) (сложить все произведения в вектор, который потом отсортировать и посчитать частоты по нему) работает немного (на 20%) быстрее.
Хороший пример, когда константа от хэш-таблицы даёт больший вклад, чем логарифм от сортировки!
impl Solution {
pub fn tuple_same_product(nums: Vec<i32>) -> i32 {
// Build vector of products for all unique pairs.
let mut products: Vec<_> = (1..nums.len())
.flat_map(|j| (0..j).map(|i| nums[i] * nums[j]).collect::<Vec<_>>())
.collect();
// Sort to group identical products.
products.sort_unstable();
// Group products, calculate frequency-based contributions, and sum them.
4 * products.chunk_by(|a, b| a == b)
.filter_map(|group| if group.len() > 1 {Some(group.len() as i32)} else {None})
.map(|freq| freq * (freq - 1))
.sum::<i32>()
}
}