【LeetCode】每日一题 2024_1_30 使循环数组所有元素相等的最少秒数（哈希、贪心、扩散）

LeetCode？启动！！！

今天的题目类型差不多是第一次见到，原来题目描述的操作是每个数 “扩散” 到整个数组，直到数组的数变的一模一样

题目：使循环数组所有元素相等的最少秒数

题目链接：2808. 使循环数组所有元素相等的最少秒数

题目描述

代码与解题思路

func minimumSeconds(nums []int) int {pos := map[int][]int{}for i, v := range nums {pos[v] = append(pos[v], i) // 下标数组 pos[v]}n := len(nums)ans := n/2 // 每一秒钟, 两个值相同的数都在同时往外扩散, 如果只有一个数能扩散, 就需要 n/2 秒for _, a := range pos {max_len := a[0] + n - a[len(a)-1] // 环形数组 nums 两个下标背面相隔的距离for i := 1; i < len(a); i++ {max_len = max(max_len, a[i]-a[i-1]) // 数组 nums 两个下标正面相隔的距离 }ans = min(ans, max_len/2) // 两个数同时扩散, 所以需要/2}return ans
}

这道题我用的思路是：

1. 先将数组中值相同的数塞进以该值为 key 的 map 中
2. 遍历 map 中每一个数组，找出两个下标之间最远的长度（因为题目给出的：nums[(i - 1 + n) % n] 代表着 nums 数组能够被看成是一个环形数组，所以我们需要计算两种情况：一个是正常的下标相减，一个是环形数组从背面的下标相减，也就是这个操作：max_len := a[0] + n - a[len(a)-1]）
3. 最后找到所有相同数下标能够扩散到对方的最小值，就是我们要求的最小秒数了（如果没有两个以上的相同数，那就只能用一个数扩散 n/2 秒了）