题解

问题描述

给定一个整数数组 nums 和一个整数 space，我们需要找到一个目标值，使得该目标值在 nums 中的出现次数最多。如果有多个目标值出现次数相同，则返回最小的目标值。

解题思路

1. 哈希表统计：使用哈希表 map 来统计每个 seed % space 的出现次数，题干中给出的等式等价为 <code>nums[n] = nums[i] + c * space，在我们知道nums[n]的前提下，可以通过nums[n]对space取余，来得到nums[i]，c是常数，不考虑。这个过程相当于是对题干等式的逆推。
2. 遍历数组：再次遍历 nums，根据哈希表中的统计信息来确定出现次数最多的目标值，注意这里的key是 seed % space。
3. 更新结果：在遍历过程中，维护一个 max 变量来记录当前最大出现次数，并更新 result 为对应的目标值。

代码实现

/*

* @lc app=leetcode id=2453 lang=rust

*

* [2453] Destroy Sequential Targets

*/

// @lc code=startuse std::collections::HashMap;

impl Solution {

pub fn destroy_targets(nums: Vec<i32>, space: i32) -> i32 {

use std::collections::HashMap;

let mut map: HashMap<i32, i32> = HashMap::new();

for &seed in &nums {

let key = seed % space;

*map.entry(key).or_insert(0) += 1;

}

let mut max = 0;

let mut result = i32::MAX;

for &seed in &nums {

match map.get(&(seed % space)) {

Some(&num) => {

if num > max {

result = seed;

max = num;

} else if num == max && seed < result {

result = seed;

}

},

None => {}

}

}

return result;

}

}

// @lc code=end

代码中使用了 Rust 的标准库 HashMap 来实现哈希表，确保了高效的查找和插入操作。通过两次遍历，时间复杂度为 O(n)，空间复杂度为 O(k)，其中 n 是数组长度，k 是不同的 seed % space 值的数量