Medium

题目描述

给你一个下标从 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 <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这道题的关键在于理解数组的"传播"机制。每秒钟，每个位置的值可以从相邻位置获得，这意味着值会逐步扩散。

核心思路：

  1. 对于每个可能的最终值（数组中出现的不同数字），计算使整个数组变为该值所需的最少秒数
  2. 关键观察：如果某个值在位置 i 和 j 都存在，那么这两个位置之间的所有位置都可以通过"扩散"变为该值
  3. 对于圆形数组，需要考虑两种扩散方向的最小值

算法步骤：

  1. 记录每个数字在数组中的所有出现位置
  2. 对于每个数字，计算相邻两个出现位置之间的最大间距
  3. 由于是圆形数组，还需要考虑首尾连接的情况
  4. 对于每个数字，所需秒数为最大间距的一半（向上取整）
  5. 返回所有可能数字中的最小秒数

为什么是间距的一半？ 因为值可以从两个方向同时扩散，所以中间位置最多需要 ⌊间距/2⌋ 秒就能被覆盖。

代码实现

class Solution {
public:
    int minimumSeconds(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> positions;
        
        // 记录每个数字的所有位置
        for (int i = 0; i < n; i++) {
            positions[nums[i]].push_back(i);
        }
        
        int result = n;
        
        for (auto& [num, pos] : positions) {
            int maxGap = 0;
            
            // 计算相邻位置之间的间距
            for (int i = 1; i < pos.size(); i++) {
                maxGap = max(maxGap, pos[i] - pos[i-1]);
            }
            
            // 计算首尾连接的间距（圆形数组）
            if (pos.size() > 1) {
                maxGap = max(maxGap, n - pos.back() + pos[0]);
            } else {
                // 只有一个位置，需要扩散到整个数组
                maxGap = n;
            }
            
            // 所需秒数为最大间距的一半
            result = min(result, maxGap / 2);
        }
        
        return result;
    }
};

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        n = len(nums)
        positions = {}
        
        # 记录每个数字的所有位置
        for i, num in enumerate(nums):
            if num not in positions:
                positions[num] = []
            positions[num].append(i)
        
        result = n
        
        for num, pos in positions.items():
            max_gap = 0
            
            # 计算相邻位置之间的间距
            for i in range(1, len(pos)):
                max_gap = max(max_gap, pos[i] - pos[i-1])
            
            # 计算首尾连接的间距（圆形数组）
            if len(pos) > 1:
                max_gap = max(max_gap, n - pos[-1] + pos[0])
            else:
                # 只有一个位置，需要扩散到整个数组
                max_gap = n
            
            # 所需秒数为最大间距的一半
            result = min(result, max_gap // 2)
        
        return result

public class Solution {
    public int MinimumSeconds(IList<int> nums) {
        int n = nums.Count;
        var positions = new Dictionary<int, List<int>>();
        
        // 记录每个数字的所有位置
        for (int i = 0; i < n; i++) {
            if (!positions.ContainsKey(nums[i])) {
                positions[nums[i]] = new List<int>();
            }
            positions[nums[i]].Add(i);
        }
        
        int result = n;
        
        foreach (var kvp in positions) {
            var pos = kvp.Value;
            int maxGap = 0;
            
            // 计算相邻位置之间的间距
            for (int i = 1; i < pos.Count; i++) {
                maxGap = Math.Max(maxGap, pos[i] - pos[i-1]);
            }
            
            // 计算首尾连接的间距（圆形数组）
            if (pos.Count > 1) {
                maxGap = Math.Max(maxGap, n - pos[pos.Count-1] + pos[0]);
            } else {
                // 只有一个位置，需要扩散到整个数组
                maxGap = n;
            }
            
            // 所需秒数为最大间距的一半
            result = Math.Min(result, maxGap / 2);
        }
        
        return result;
    }
}

var minimumSeconds = function(nums) {
    const n = nums.length;
    const positions = new Map();
    
    // 记录每个数字的所有位置
    for (let i = 0; i < n; i++) {
        if (!positions.has(nums[i])) {
            positions.set(nums[i], []);
        }
        positions.get(nums[i]).push(i);
    }
    
    let result = n;
    
    for (const [num, pos] of positions) {
        let maxGap = 0;
        
        // 计算相邻位置之间的间距
        for (let i = 1; i < pos.length; i++) {
            maxGap = Math.max(maxGap, pos[i] - pos[i-1]);
        }
        
        // 计算首尾连接的间距（圆形数组）
        if (pos.length > 1) {
            maxGap = Math.max(maxGap, n - pos[pos.length-1] + pos[0]);
        } else {
            // 只有一个位置，需要扩散到整个数组
            maxGap = n;
        }
        
        // 所需秒数为最大间距的一半
        result = Math.min(result, Math.floor(maxGap / 2));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(n)

说明：

  • 时间复杂度：需要遍历数组一次记录位置，然后遍历所有不同的数字计算间距，总体为 O(n)
  • 空间复杂度：需要额外空间存储每个数字的位置信息，最坏情况下所有元素都不同，为 O(n)