LeetCode 2808. Minimum Seconds to Equalize a Circular Array

You are given a 0-indexed array nums containing n integers.

At each second, you perform the following operation on the array:

• For every index i in the range [0, n - 1], replace nums[i] with either nums[i], nums[(i - 1 + n) % n], or nums[(i + 1) % n].

Note that all the elements get replaced simultaneously.

Return the minimum number of seconds needed to make all elements in the array nums equal.

Example 1:

Input: nums = [1,2,1,2]

Output: 1

Explanation: 

We can equalize the array in 1 second in the following way: - At 1st second, replace values at each index with [nums[3],nums[1],nums[3],nums[3]]. After replacement, nums = [2,2,2,2]. It can be proven that 1 second is the minimum amount of seconds needed for equalizing the array.

Example 2:

Input: nums = [2,1,3,3,2]

Output: 2

Explanation:

We can equalize the array in 2 seconds in the following way: - At 1st second, replace values at each index with [nums[0],nums[2],nums[2],nums[2],nums[3]]. After replacement, nums = [2,3,3,3,3]. - At 2nd second, replace values at each index with [nums[1],nums[1],nums[2],nums[3],nums[4]]. After replacement, nums = [3,3,3,3,3]. It can be proven that 2 seconds is the minimum amount of seconds needed for equalizing the array.

Example 3:

Input: nums = [5,5,5,5]

Output: 0

Explanation: 

We don't need to perform any operations as all elements in the initial array are the same.

Constraints:

• 1 <= n == nums.length <= 105

• 1 <= nums[i] <= 109

------------------------------------------

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

解释：不需要执行任何操作，因为一开始数组中的元素已经全部相等。

Runtime: 77 ms, faster than 49.12% of Java online submissions for Minimum Seconds to Equalize a Circular Array.

Memory Usage: 90.3 MB, less than 6.80% of Java online submissions for Minimum Seconds to Equalize a Circular Array.

------------------------------

如果数组中没有相同的数字，那么肯定话费的时间是最长的也就是n/2了，既然可以改变左右2个相邻的数字，那么我们将相同元素的索引值放到一个链表里面，注意最后加一个n，这样就是环形链表了，

然后依次去判断2个index的最值即可，

最后跟n/2取最小值即可；

下面是代码：