Leetcode 2453. Destroy Sequential Targets | rust 实现

题解

问题形貌

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

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

代码实现

1. /*
2. * @lc app=leetcode id=2453 lang=rust
3. *
4. * [2453] Destroy Sequential Targets
5. */
7. // @lc code=startuse std::collections::HashMap;
8. impl Solution {
9.     pub fn destroy_targets(nums: Vec<i32>, space: i32) -> i32 {
10.         use std::collections::HashMap;
11.    
12.         let mut map: HashMap<i32, i32> = HashMap::new();
13.         for &seed in &nums {
14.             let key = seed % space;
15.             *map.entry(key).or_insert(0) += 1;
16.         }
17.    
18.         let mut max = 0;
19.         let mut result = i32::MAX;
20.         for &seed in &nums {
21.             match map.get(&(seed % space)) {
22.                 Some(&num) => {
23.                     if num > max {
24.                         result = seed;
25.                         max = num;
26.                     } else if num == max && seed < result {
27.                         result = seed;
28.                     }
29.                 },
30.                 None => {}
31.             }
32.         }
33.    
34.         return result;
35.     }
36. }
37. // @lc code=end

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。