What is the primary pattern for solving 'Minimum Seconds to Equalize a Circular Array'?

The primary pattern involves array scanning and hash lookup, where you calculate the frequency of each value and determine the minimum number of seconds to make all elements equal.

How do you calculate the minimum number of seconds?

You calculate the number of seconds by checking how many elements need to change for each target value, then choosing the one with the minimal required seconds.

Is the solution for this problem based on greedy techniques?

The solution relies on identifying the optimal target value based on frequency, which could be seen as a greedy approach to minimize transformations.

How do hash tables help in solving this problem?

Hash tables help by allowing you to count the frequency of each element efficiently, enabling quick identification of the most frequent element, which is key to minimizing transformation time.

What should I do if all elements in the array are already equal?

If all elements are the same, no transformations are needed, so the minimum number of seconds is zero.

#2808

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个下标从 0 开始长度为 n 的数组 nums 。每一秒，你可以对数组执行以下操作：对于范围在 [0, n - 1] 内的每一个下标 i ，将 nums[i] 替换成 nums[i] ， nums[(i - 1 + n) % n] 或者 nums[(i + 1) % n] 三者之一。注意…

数组哈希表

题目描述

给你一个下标从 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⁹

lightbulb

解题思路

方法一：枚举

我们假设最终所有元素都变成了 $x$ ，那么 $x$ 一定是数组中的某个元素。

数字 $x$ 每一秒都可以向左右两边扩展一位，如果有多个相同的 $x$ ，那么扩展完整个数组所需要的时间，就取决于相邻两个 $x$ 之间的最大间距。

因此，我们枚举每个元素作为最终的 $x$ ，计算出每个 $x$ 中相邻两个元素之间的最大间距，记为 $t$ ，那么最终答案就是 $\min\limits_{x \in nums} \left\lfloor \frac{t}{2} \right\rfloor$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def minimumSeconds(self, nums: List[int]) -> int:
        d = defaultdict(list)
        for i, x in enumerate(nums):
            d[x].append(i)
        ans = inf
        n = len(nums)
        for idx in d.values():
            t = idx[0] + n - idx[-1]
            for i, j in pairwise(idx):
                t = max(t, j - i)
            ans = min(ans, t // 2)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of hash map usage for counting frequencies.
question_mark
Check for ability to identify the most frequent element and consider it as a candidate target.
question_mark
Evaluate how efficiently the candidate target selection process is performed.

warning

常见陷阱

外企场景

error
Misunderstanding the problem and focusing on inefficient operations like sorting the array.
error
Failing to account for all possible target values in the array, which could lead to suboptimal solutions.
error
Neglecting to handle edge cases like arrays where all elements are already equal.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Variation 1: Include additional constraints on the range of values in the array.
arrow_right_alt
Variation 2: Require that all replacements must be made in parallel within the same second.
arrow_right_alt
Variation 3: Add a constraint where the number of replacements must be minimized.

help

常见问题

外企场景

继续练习

#2813 子序列最大优雅度 #2815 数组中的最大数对和 #2799 统计完全子数组的数目