【算法】【环形数组处理技巧、枚举】力扣2808. 使循环数组所有元素相等的最少秒数

2808. 使循环数组所有元素相等的最少秒数

文章目录

• 【算法】力扣2808. 使循环数组所有元素相等的最少秒数
• • 题目描述
  • • 输入输出示例
  • 解题思路
  • • 算法步骤
    • Python3代码实现
    • C++代码实现
    • GO实现
    • 复杂度分析
  • 总结

---

【算法】力扣2808. 使循环数组所有元素相等的最少秒数

题目描述

在这道题目中，我们得到了一个循环数组nums，其长度为n。我们的目标是通过每秒钟进行一次数组变换，最终使得所有元素相等。数组变换的规则是，对于数组中的任意元素nums[i]，可以将其替换为其左侧或右侧元素（考虑数组为循环数组）。题目要求我们找到实现数组所有元素相等的最少秒数。

输入输出示例

示例 1：

• 输入：nums = [1,2,1,2]
• 输出：1
• 解释： 按照题目描述的替换规则，1秒内我们可以将数组中的所有元素变为2。

示例 2：

• 输入：nums = [2,1,3,3,2]
• 输出：2
• 解释： 通过两次替换操作，我们可以将数组变成[3,3,3,3,3]。

示例 3：

• 输入：nums = [5,5,5,5]
• 输出：0
• 解释： 数组已经是所有元素相等的状态，无需进行操作。

解题思路

本题的关键在于理解变换操作对数组元素的影响。考虑到可替换的元素为nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n]，即数组是循环的，我们可以将原数组复制并连接到其自身的末尾，从而形成一个方便处理的扩展数组。这样，原本循环的边界条件就变成了顺序数组的处理问题。

算法步骤

1. 利用哈希表存储每个元素及其所有出现的位置。
2. 枚举原数组中所有不同的元素，计算如果以该元素作为最终相等元素所需的时间。
3. 对于每个元素，找到其在数组中每最近一对之间的距离所对应的最大修改秒数。
4. 记录使元素相等的最少秒数，即所有最大距离中的最小值。

Python3代码实现

from collections import defaultdict
from itertools import pairwise

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        # 哈希表存储每个元素及其在数组中的位置
        ele_idxes = defaultdict(list)

        # 遍历数组，填充哈希表
        for i, x in enumerate(nums):
            ele_idxes[x].append(i)
        n = len(nums)
        ans = n

        # 枚举所有不同的元素
        for idxes in ele_idxes.values():
            curr = 0
            # 数组扩展，形成循环数组的线性表示
            idxes.append(idxes[0] + n)

            # 计算最大间隔
            for i, j in pairwise(idxes):
                curr = max(curr, (j - i) // 2)

            # 更新答案
            ans = min(ans, curr)
        
        return ans

C++代码实现

class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        unordered_map<int, vector<int>> idxes;

        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            idxes[nums[i]].push_back(i);
        }

        int ans = n;

        for (auto &[ele, ele_idx] : idxes) {
            int curr = 0;
            ele_idx.push_back(ele_idx[0] + n);
            for (int i = 0, j = 1; j < ele_idx.size(); ++i, ++j) {
                int left = ele_idx[i], right = ele_idx[j];
                curr = max(curr, (right - left) / 2);
            }
            ans = min(curr, ans);
        }
        return ans;
    }
};

GO实现

func minimumSeconds(nums []int) int {
    pos := map[int][]int{}
    for i, x := range nums {
        pos[x] = append(pos[x], i)
    }

    n := len(nums)
    ans := n

    for _, a := range pos {
        curr := 0
        a = append(a, n + a[0])
        for i := 1; i < len(a); i++ {
            left := a[i - 1]
            right := a[i]
            curr = max(curr, (right - left) / 2)
        }
        ans = min(ans, curr)
    }
    return ans

}

复杂度分析

• 时间复杂度：$O(n)$，其中$n$是数组nums的长度。我们需要遍历数组来填充哈希表，并对每个不同元素计算最大间隔。
• 空间复杂度：$O(n)$，用于存储哈希表及其元素的位置。

总结

这道题目考验了我们对循环数组以及枚举技巧的理解。通过将循环数组转换为线性数组，我们简化了问题的复杂度。第一眼，我的思路是用BFS模拟搜索，后面我发现用BFS复杂度偏高；第二眼，其实直接枚举的复杂度与直接模拟操作 + BFS相比要低很多。所以说，尽管“枚举”一词听起来不那么高级，但是善用枚举却能帮助我们更快速甚至更高效地解决问题。