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

难度: 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⁵
1 <= nums[i] <= 10⁹

Submission

运行时间: 119 ms

内存: 43.4 MB

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        n = len(nums)
        leftMost = dict()
        rightMost = dict()
        dist = dict()
        ans = n
        for i, num in enumerate(nums):
            if num not in leftMost:
                leftMost[num] = i
                rightMost[num] = i
            else:
                if num not in dist:
                    dist[num] = []
                dist[num].append(i-rightMost[num])
                rightMost[num] = i
        for key in dist:
            dist[key].append(leftMost[key]+n-rightMost[key])
            ans = min(ans, max(dist[key]))
        return (ans//2)

Explain

该题解的思路是首先统计数组中每个不同元素的最左出现位置(leftMost)和最右出现位置(rightMost)，然后对于每个元素计算其在数组中的所有相邻出现位置之间的距离，并将这些距离存储在一个字典(dist)中。最后，对于每个元素，将其最左出现位置到最右出现位置的距离也加入到dist中。这样，对于每个元素，dist中存储的就是将其转换为相同元素所需的最小步数的候选值。最后，遍历dist，找到最小的最大距离，即为所需的最小秒数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        n = len(nums)
        leftMost = dict()
        rightMost = dict()
        dist = dict()
        ans = n
        for i, num in enumerate(nums):
            if num not in leftMost:
                leftMost[num] = i
                rightMost[num] = i
            else:
                if num not in dist:
                    dist[num] = []
                dist[num].append(i-rightMost[num])
                rightMost[num] = i
        for key in dist:
            dist[key].append(leftMost[key]+n-rightMost[key])
            ans = min(ans, max(dist[key]))
        return (ans//2)

Explore

在题解中，统计每个元素的最左和最右出现位置帮助确定元素在数组中分布的范围。这是因为要使数组所有元素相等，我们需要考虑将数组的一部分或全部转变为同一个元素。知道元素的最左和最右出现位置，可以帮助我们计算如果选择该元素作为目标值，需要覆盖的最长连续子数组的长度。这样，我们可以更准确地估计出使整个数组元素相等的最少操作次数。

在题解中，距离存储字典（dist）的键是数组中的元素，而值是一个列表，这个列表存储的是该元素的所有相邻出现位置之间的距离，以及从最左出现位置到最右出现位置的循环距离。例如，如果某个元素在索引2, 5, 9出现过，dist将会记录从5到2的距离，从9到5的距离，以及从2回到9的循环距离。这样的结构帮助识别将数组中的所有元素转换为此元素时，每个转换步骤中必须覆盖的最大距离，从而确定最优的转换策略。

将最左出现位置到最右出现位置的距离加入到dist中是为了考虑循环数组的特性。在循环数组中，数组的末端元素可以直接与数组的起始元素相邻。因此，计算从最左出现位置到最右出现位置的距离，实际上是计算闭合循环的一部分，即从最右边的元素跳转到最左边的元素所需覆盖的距离。这样做可以确保在计算所有元素转换为同一元素时，考虑到数组的循环性，从而找到覆盖整个数组所需的最小最大步数。

题解中进行(ans//2)操作的原因是，在计算距离时，每次计算的是从一个元素到另一个相同元素的距离，这实际上是两个步骤的距离（即从一个位置移动到下一个位置，然后再移动到下一个相同元素的位置）。因此，为了得到将所有元素变为相同元素所需的实际秒数（即操作次数），需要将累计的距离除以2，从而得到单次操作的平均最大距离，这是因为每次操作可以同时改变两个位置的元素。