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

leetcode
1.4k words

https://leetcode.cn/problems/minimum-seconds-to-equalize-a-circular-array/description/

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        unordered_map<int, vector<int>> ump;
        for (int i = 0; i < nums.size();++i) {
            ump[nums[i]].push_back(i);
        }
        int res = nums.size();
        for (auto& u : ump) {
            int mx = u.second[0] + nums.size() - u.second.back();
            for (int i = 1; i < u.second.size(); ++i) {
                int dis = u.second[i] - u.second[i - 1];
                mx = max(mx, dis);
            }
            res = min(res, mx / 2);
        }
        return res;
    }
};

解释

这是一个关于数组转换的优化问题。题目要求找到将数组中所有元素变为相等所需的最少秒数。每一秒，您可以将数组中的每个元素 nums[i] 替换为 nums[i]、nums[(i - 1 + n) % n] 或 nums[(i + 1) % n] 中的任意一个。这里 % n 确保索引在数组范围内。由于所有元素会被同时替换，这增加了问题的复杂性。

解决这个问题的关键是找出数组中每个唯一元素相邻出现位置之间的最大间隔，然后基于这个最大间隔来确定转换所需的时间。下面是代码解释：

  1. 构建哈希表 mp：

    1
    2
    3
    4
    unordered_map<int, vector<int>> mp;
    for (int i = 0; i < n; ++i) {
        mp[nums[i]].push_back(i);
    }

    这部分代码将数组 nums 中每个唯一元素的所有出现位置索引存储在哈希表 mp 中。

  2. 计算最大间隔：

    1
    2
    3
    4
    5
    6
    7
    for (auto& pos : mp) {
        int mx = pos.second[0] + n - pos.second.back();
        for (int i = 1; i < pos.second.size(); ++i) {
            mx = max(mx, pos.second[i] - pos.second[i - 1]);
        }
        res = min(res, mx / 2);
    }

    对于哈希表 mp 中的每个元素：

    • 首先，计算第一个出现位置到数组末尾和数组末尾到最后一个出现位置的距离之和。
    • 然后，计算该元素相邻出现位置之间的最大间隔。
    • 将最大间隔的一半与当前的 res 比较，并更新 res 为这两者中的较小值。

在此问题中，最大间隔的一半实际上是转换过程中的关键参数。由于每秒可以将任何元素替换为其相邻元素，最大间隔的一半代表了使所有元素变得相等所需的最小步骤数。例如，如果最大间隔为6，那么在3秒内，通过不断替换相邻元素，可以使所有元素变得相等（无论最初的元素值是什么）。

因此，这个算法通过计算每个唯一元素之间的最大间隔来确定将整个数组转换为单一值所需的最少秒数。

Comments