做网站的app有什么作用,榆林城乡建设规划官方网站,wordpress微信h5登录页面,杭州做销售去哪个网站好2808. 使循环数组所有元素相等的最少秒数
难度: 中等
题目大意#xff1a; 给你一个下标从 0 开始长度为 n 的数组 nums 。 每一秒#xff0c;你可以对数组执行以下操作#xff1a; 对于范围在 [0, n - 1] 内的每一个下标 i #xff0c;将 nums[i] 替换成 nums[i] 给你一个下标从 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(vectorint nums) {int n nums.size();unordered_mapint, vectorint 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)
结束了
