衡水商城网站制作东莞网站建设推广技巧
2808. 使循环数组所有元素相等的最少秒数
难度: 中等
题目大意：
给你一个下标从 0 开始长度为
n的数组nums。每一秒，你可以对数组执行以下操作：
- 对于范围在
[0, n - 1]内的每一个下标i，将nums[i]替换成nums[i]，nums[(i - 1 + n) % n]或者nums[(i + 1) % n]三者之一。注意，所有元素会被同时替换。
请你返回将数组
nums中所有元素变成相等元素所需要的 最少 秒数。提示：
1 <= n == nums.length <= 10^51 <= nums[i] <= 10^9示例 1：
输入：nums = [1,2,1,2] 输出：1 解释：我们可以在 1 秒内将数组变成相等元素： - 第 1 秒，将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后，nums = [2,2,2,2] 。 1 秒是将数组变成相等元素所需要的最少秒数。
分析
首先我们是不知道最终是会被哪个数给占据的，不一定是数量最多的数字，所以我们要枚举会被哪个数占据，假设是x，那么如果全部被x占据，那么最终需要多少秒能够把全部的数组全部占满呢，思考一下应该是相邻两个x的位置的最大值/2，所以我们只需要存一下每个数字对应的下标就可以了， 注意这个是环形的，所以最左边x的是和最右边的x向对应的
哈希表 + 枚举
class Solution {
public:int minimumSeconds(vector<int>& nums) {int n = nums.size();unordered_map<int, vector<int>> pos;for (int i = 0; i < n; i ++) {int x = nums[i];pos[x].push_back(i);}int res = 1e9;for (auto& [_, p] : pos) {int locmx = p[0] + n - p.back(); // 最左侧和最右侧的数字for (int i = 1; i < p.size(); i ++) {locmx = max(locmx, p[i] - p[i - 1]);}res = min(res, locmx >> 1);}return res;}
};
时间复杂度: O ( n ) O(n) O(n)
结束了