class Solution {
public:
int minimumSeconds(vector<int>& nums) {
}
};
6956. 使循环数组所有元素相等的最少秒数
给你一个下标从 0 开始长度为 n 的数组 nums 。
每一秒，你可以对数组执行以下操作：
[0, n - 1] 内的每一个下标 i ，将 nums[i] 替换成 nums[i] ，nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。注意，所有元素会被同时替换。
请你返回将数组 nums 中所有元素变成相等元素所需要的 最少 秒数。
示例 1：
输入：nums = [1,2,1,2] 输出：1 解释：我们可以在 1 秒内将数组变成相等元素： - 第 1 秒，将每个位置的元素分别变为 [nums[3],nums[1],nums[3],nums[3]] 。变化后，nums = [2,2,2,2] 。 1 秒是将数组变成相等元素所需要的最少秒数。
示例 2：
输入：nums = [2,1,3,3,2] 输出：2 解释：我们可以在 2 秒内将数组变成相等元素： - 第 1 秒，将每个位置的元素分别变为 [nums[0],nums[2],nums[2],nums[2],nums[3]] 。变化后，nums = [2,3,3,3,3] 。 - 第 2 秒，将每个位置的元素分别变为 [nums[1],nums[1],nums[2],nums[3],nums[4]] 。变化后，nums = [3,3,3,3,3] 。 2 秒是将数组变成相等元素所需要的最少秒数。
示例 3：
输入：nums = [5,5,5,5] 输出：0 解释：不需要执行任何操作，因为一开始数组中的元素已经全部相等。
提示：
1 <= n == nums.length <= 1051 <= nums[i] <= 109原站题解
cpp 解法, 执行用时: 296 ms, 内存消耗: 142 MB, 提交时间: 2024-01-30 09:45:41
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++) {
pos[nums[i]].push_back(i);
}
int ans = n;
for (auto &[_, a] : pos) {
int mx = n - a.back() + a[0];
for (int i = 1; i < a.size(); ++i) {
mx = max(mx, a[i] - a[i - 1]);
}
ans = min(ans, mx / 2); // 最后再除 2
}
return ans;
}
};
java 解法, 执行用时: 86 ms, 内存消耗: 73.5 MB, 提交时间: 2023-08-07 15:41:43
class Solution {
public int minimumSeconds(List<Integer> nums) {
int n = nums.size();
Map<Integer, List<Integer>> map = new HashMap<>(); // 记录每个元素出现的位置下标
for(int i = 0; i < nums.size(); i++){
if(!map.containsKey(nums.get(i))) map.put(nums.get(i), new ArrayList<>());
map.get(nums.get(i)).add(i);
}
int ans = n / 2;
for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){
List<Integer> list = entry.getValue();
list.add(list.get(0) + n);
int mx = -1;
for(int j = 1; j < list.size(); j++){
mx = Math.max(mx, (list.get(j) - list.get(j-1)) / 2);
}
ans = Math.min(ans, mx);
}
return ans;
}
}
golang 解法, 执行用时: 200 ms, 内存消耗: 26.5 MB, 提交时间: 2023-08-07 15:41:19
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 {
a = append(a, a[0]+n)
mx := 0
for i := 1; i < len(a); i++ {
mx = max(mx, (a[i]-a[i-1])/2)
}
ans = min(ans, mx)
}
return ans
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 576 ms, 内存消耗: 51.7 MB, 提交时间: 2023-08-07 15:40:29
'''
把问题看成扩散元素
1.最终所有元素一定变成了一个在 nums 中的数, 枚举这个数。
2.考虑把数字 x「扩散」到其它位置，那么每一秒 x 都可以向左右扩散一位。
多个相同数字 x 同时扩散，那么扩散完整个数组的耗时，就取决于相距最远的两个相邻的 x。
3.统计所有相同数字的下标，记到一个哈希表 pos 中。
本题数组可以视作是环形的，假设最左边的 x 的下标是 i，
只需要在 pos[x] 列表末尾添加一个 i+n，就可以转换成非环形数组处理了。
'''
class Solution:
def minimumSeconds(self, nums: List[int]) -> int:
pos = defaultdict(list)
for i, x in enumerate(nums):
pos[x].append(i)
ans = n = len(nums)
for a in pos.values():
a.append(a[0] + n)
mx = max((j - i) // 2 for i, j in pairwise(a))
ans = min(ans, mx)
return ans