На практических масштабах решение со сложностью 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>()
}
}
Можно предоставить также и решение за один проход.
Мне кажется, что оно менее изящно. Но всё-равно имеет право быть упомянутым:
use std::cmp::Ordering;
impl Solution {
pub fn longest_monotonic_subarray(nums: Vec<i32>) -> i32 {
nums.windows(2).fold((1, 1, 1), |(max_chain, inc_chain, dec_chain), w| {
match w[1].cmp(&w[0]) {
// extend decreasing chain; reset increasing chain; update max_chain
Ordering::Less => (max_chain.max(dec_chain + 1), 1, dec_chain + 1),
// reset both chains on equal elements
Ordering::Equal => (max_chain, 1, 1),
// extend increasing chain; reset decreasing chain; update max_chain
Ordering::Greater => (max_chain.max(inc_chain + 1), inc_chain + 1, 1),
}
}).0
}
}
@ 
finder
Посмотри, пожалуйста, почему обещаемая в документации "быстрая ссылка на википедию" не срабатывает у меня:
[[Алгоритм_Кнута_—Морриса—_Пратта]]
перейти
Я, видимо, туплю, хеш-таблицы-то зачем? Двух массивов хватило бы?
перейти
Опять я провалил АА, что ж такое-то.
Если серьезно, то это пример, когда литкод-стайл измеряет не просто не то же самое, что нужно потом на работе, а прямо противоположную вещь. Сама задача очень простая, но, оказывается, можно ошибиться вот так. При этом в работе думать о том, что фраза "Даны шарики с уникальными метками от 0 до limit (всего limit + 1 шариков)" может означать, что их может оказаться миллиард, натурально вредно. Речь не о том, что не нужно оптимизировать заранее (иначе пол-литкода можно было бы стереть), но ограничения на количества объектов и операций обычно читаются из физического смысла происходящего. Запросов или, там, транзакций может быть миллиард, пользователей уже вряд ли, если вы не Мета, а шариков будут десятки, может, сотни. Особенно если они перенумерованные (а не снабженные, скажем, guid-ами).
перейти
Как будто бы, ты слишком строк к себе!
Не понять интервьюера не является грехом. Важно же, просто уметь быстро перестраивать своё решение, если что-то было изначально понято неправильно. И как раз обладание таким скилом, на мой взгляд, является гипер-полезным в рабочем процессе. И отлично, если ты его сумел показать на собеседовании!
перейти
В ограничениях задачи - шариков может быть до миллиарда: никто не гарантирует, что все бесцветные шарики в памяти уложатся.
В подходе с хэш-таблицей мы только цветные шарики храним в памяти, а их не больше, чем число операций.
перейти